2차원 좌표 평면 위에 1 ~ n의 번호가 있는 도시가 있습니다. 각 도시는 2차원 좌표 평면에서 점으로 나타냅니다. 또한 도시 사이를 이동하기 위한 자동차 도로가 있습니다. 각 도로는 2차원 좌표 평면에서 x축 혹은 y축에 평행한 선분으로 나타냅니다. 좌표 평면상에서 교차하거나 만나는 서로 다른 도로는 해당 지점에서 연결됩니다. 도로가 연결된 지점을 활용해 여러 도로를 경유할 수 있습니다.

• 위 그림에서 파란색 마름모는 도시를 나타냅니다. 각 도시는 1 ~ 4의 번호가 있습니다.
• 굵은 회색 선분은 도로를 나타냅니다.
• 모든 도시는 도로가 지나가는 위치에 있습니다.

모든 도로의 정중앙에는 과속 단속 카메라가 있습니다. 과속 단속 카메라가 있는 지점을 지나갈 때는 해당 카메라의 지정된 제한 속도이하로 주행해야 합니다. 만약 한 지점에 카메라가 여러 개 있다면, 그중 제한 속도가 가장 낮은 카메라의 제한을 따릅니다.

• 각 도로의 정중앙에 있는 원은 해당 위치에 있는 단속 카메라의 제한 속도를 나타냅니다.

당신은 1번 도시에서 출발하며, 출발 직전에 단 하나의 속도 v를 정하고 도착할 때까지 일정한 속도를 유지합니다. 2 ~ n번 도시 중 한 곳으로 갈 때, 각 도시마다 카메라 제한 속도를 지키면서 이동 가능한 최고 속도를 구해야 합니다.

다음은 위 예시에서 2, 3, 4번 도시로 갈 때, 일정한 최고 속도를 내기 위한 경로입니다.

• 위와 같은 경로로 이동하면 최고 70까지 속도를 낼 수 있습니다.

• 위와 같은 경로로 이동하면 최고 50까지 속도를 낼 수 있습니다.

• 위와 같은 경로로 이동하면 카메라를 지나치지 않으므로 제한 없이 속도를 낼 수 있습니다.

각 도시의 위치를 담은 2차원 정수 배열 city와 도로의 정보를 담은 2차원 정수 배열 road가 매개변수로 주어집니다. 이때 1번 도시에서 출발해 각 2번 ~ n번 도시로 갈 때, 가능한 최고 속도를 도시 번호 순서대로 길이가 n-1인 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 카메라를 지나치지 않고 갈 수 있는 도시는 최고 속도 대신 0을 담습니다.

제한사항

• 2 ≤ city의 길이 = n ≤ 100
  • city[i]는 [x, y] 형태이며, i+1번 도시의 위치가 (x, y)임을 의미합니다.
  • 모든 도시는 도로가 지나가는 위치에 있으며, 각 도시의 위치가 서로 겹치지 않습니다.
• 1 ≤ road의 길이 = m ≤ 1,000
  • road의 원소는 [x1, y1, x2, y2, limit] 형태이며, 정중앙에 있는 카메라의 제한 속도가 limit인 (x1, y1)과 (x2, y2)를 잇는 선분 형태의 도로를 나타냅니다. 카메라의 위치는 도시의 위치와 겹치지 않습니다.
  • 모든 도로는 x축 혹은 y축에 평행하며, 길이가 짝수입니다.
  • x1 ≤ x2
  • y1 ≤ y2
  • 1 ≤ limit ≤ 1,000,000
  • 서로 다른 두 도로는 최대 한 점에서만 만납니다.
• 주어지는 모든 좌표의 절댓값은 10⁹ 이하의 정수입니다.
• 모든 도시와 도로는 서로 연결되어 있습니다.

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

한 지점에 카메라가 여러 개 있는 경우, 그중 제한 속도가 가장 낮은 카메라의 제한을 따르므로 전체 그림은 아래와 같습니다.

• 2번 도시는 카메라를 지나치지 않고 갈 수 있습니다.
• 3번 도시는 최고 30까지 속도를 낼 수 있습니다.
• 4, 5번 도시는 최고 29까지 속도를 낼 수 있습니다.

따라서 [0, 30, 29, 29]를 return 합니다.