시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB113375.000%

문제

There are n cities in Byteland numbered from 1 to n and city 1 is the capital. All cities's location are on a w × h grid, which has an integer coordinate (x, y) (1 ≤ xw, 1 ≤ yh). Different cities share different locations.

There are m portals in Byteland numbered from 1 to m. Portal i is located at city pi, with some constraints ti, Li, Ri, Di, Ui. With portal i, Kevin can spend ti (ti > 0) transporting from pi to a city j where its location (x,y) satisfies LixRi, DiyUi (1 ≤ LiRiw, 1 ≤ DiUih). One city may have many portals.

Starting from city 1, Kevin wants to know the least time needed to go to every city i. Note that Kevin can only transport with portals and only using portals take time. It is guaranteed that there is at least a way to go to each city i from city 1.

입력

The first line contains four integers n, m, w, h.

In the following n lines, each line contains two integers xi, yi, indicating the coordinate of city i.

In the following m lines, each line contains six integers pi, ti, Li, Ri, Di, Ui, indicating constraints of portal i.

출력

In line i, output the answer to city i + 1.

제한

For all test cases, 1 ≤ n ≤ 70000, 1 ≤ m ≤ 150000, 1 ≤ w, hn, 1 ≤ ti ≤ 10000.

예제 입력 1

5 3 5 5
1 1
3 1
4 1
2 2
3 3
1 123 1 5 1 5
1 50 1 5 1 1
3 10 2 2 2 2

예제 출력 1

50
50
60
123