점프
시간 제한1초메모리 제한512 MB
격자 위의 도시들과 한 도시에서 직사각형 안의 임의 도시로 이동하는 포털이 주어질 때, 1번 도시에서 모든 도시까지의 최단 시간을 구한다.
문제
바이틀랜드에는 1번부터 n번까지 번호가 붙은 n개의 도시가 있고, 1번 도시가 수도이다. 모든 도시는 w × h 격자 위의 정수 좌표 (x, y) (1 ≤ x ≤ w, 1 ≤ y ≤ h)에 위치한다. 서로 다른 도시는 서로 다른 위치를 차지한다.
바이틀랜드에는 1번부터 m번까지 번호가 붙은 m개의 포털이 있다. 포털 i는 도시 pi에 있으며, 제약 ti, Li, Ri, Di, Ui를 가진다. 포털 i를 이용하면 Kevin은 ti (ti > 0)의 시간을 들여 pi에서 좌표 (x,y)가 Li ≤ x ≤ Ri, Di ≤ y ≤ Ui를 만족하는 도시 j로 이동할 수 있다 (1 ≤ Li ≤ Ri ≤ w, 1 ≤ Di ≤ Ui ≤ h). 한 도시에 여러 포털이 있을 수 있다.
1번 도시에서 출발하여 Kevin은 모든 도시 i로 가는 데 필요한 최소 시간을 알고 싶어 한다. Kevin은 포털로만 이동할 수 있고, 포털을 사용할 때만 시간이 든다. 각 도시 i에 1번 도시에서 갈 수 있는 방법이 적어도 하나 있음이 보장된다.
입력
첫째 줄에 네 정수 n, m, w, h가 주어진다.
다음 n개 줄에 각각 두 정수 xi, yi가 주어지며, 이는 도시 i의 좌표를 나타낸다.
다음 m개 줄에 각각 여섯 정수 pi, ti, Li, Ri, Di, Ui가 주어지며, 이는 포털 i의 제약을 나타낸다.
출력
i번째 줄에 도시 i + 1에 대한 답을 출력한다.
제한
모든 테스트 케이스에 대해 1 ≤ n ≤ 70000, 1 ≤ m ≤ 150000, 1 ≤ w, h ≤ n, 1 ≤ ti ≤ 10000.