19655번 - Jump 다국어

문제

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 ≤ x ≤ w, 1 ≤ y ≤ h). Different cities share different locations.

There are m portals in Byteland numbered from 1 to m. Portal i is located at city p_i, with some constraints t_i, L_i, R_i, D_i, U_i. With portal i, Kevin can spend t_i (t_i > 0) transporting from p_i to a city j where its location (x,y) satisfies L_i ≤ x ≤ R_i, D_i ≤ y ≤ U_i (1 ≤ L_i ≤ R_i ≤ w, 1 ≤ D_i ≤ U_i ≤ h). 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 x_i, y_i, indicating the coordinate of city i.

In the following m lines, each line contains six integers p_i, t_i, L_i, R_i, D_i, U_i, 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, h ≤ n, 1 ≤ t_i ≤ 10000.

힌트