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 70000$, $1\le m\le 150000$, $1\le w,h\le n$, $1\le t_i\le 10000$.

Test Case	$1\le n\le$	$1\le m\le$	Additional Constraints
1~8	$100$	$100$	None
9~13	$50000$	$100000$	Every portal can reach exactly 1 city, and $L_i=R_i,D_i=U_i$
14~18	$50000$	$100000$	$h=1$
19~22	$25000$	$50000$	None
23~25	$70000$	$150000$

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