There are ~n~ cities in Byteland numbered from ~1~ to ~n~ and city ~1~ is the capital. All cities' locations are on a ~w \times h~ grid, which has an integer coordinate ~(x,y)~ ~(1 \le x \le w, 1 \le y \le 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 \le x \le R_i, D_i \le y \le U_i~ ~(1 \le L_i \le R_i \le w, 1 \le D_i \le U_i \le 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~.

Input Specification

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~.

Constraints

For all test cases, ~1 \le n \le 70\,000~, ~1 \le m \le 150\,000~, ~1 \le w,h \le n~, ~1 \le t_i \le 10\,000~.

Test Case	~1 \le n \le~	~1 \le m \le~	Additional Constraints
1~8	~100~	~100~	None
9~13	~50\,000~	~100\,000~	Every portal can reach exactly 1 city, and ~L_i = R_i, D_i=U_i~
14~18	~50\,000~	~100\,000~	~h = 1~
19~22	~25\,000~	~50\,000~	None
23~25	~70\,000~	~150\,000~

Output Specification

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

Sample Input 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

Sample Output 1

50
50
60
123