The Kingdom of Fleas has $n$ cities, numbered $1$ to $n$, with city $1$ being the capital. All cities are located on a $w \times h$ grid. Each city has an integer coordinate $(x, y)$ ($1 \le x \le w, 1 \le y \le h$), and no two cities share the same coordinates.

There are $m$ jump devices in the Kingdom of Fleas, numbered $1$ to $m$. The $i$-th jump device is located in city $p_i$ and has parameters $t_i, L_i, R_i, D_i, U_i$. By using this jump device, a flea can spend $t_i$ ($t_i > 0$) units of time to jump from city $p_i$ to any city whose coordinates $(x, y)$ satisfy $L_i \le x \le R_i$ and $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$). Note that a city may contain multiple jump devices, or it may contain none at all.

Due to the large distances between cities, fleas must rely on jump devices for travel. Specifically, a trip passes through a sequence of cities $a_0, a_1, \dots, a_k$. During this trip, the sequence of jump devices used is $b_1, b_2, \dots, b_k$. Each city can appear in the sequence $\{a_j\}$ any number of times, and each jump device can appear in the sequence $\{b_j\}$ any number of times. For each $j$ ($1 \le j \le k$), the jump device $b_j$ is located in city $a_{j-1}$, and the flea can jump from city $a_{j-1}$ to city $a_j$ using this device. This is called a trip from city $a_0$ to city $a_k$, consisting of $k$ jumps with a total cost of $\sum_{i=1}^k t_{b_i}$ units of time.

The King of Fleas wants to know, for every city other than the capital (city $1$), the minimum time required to travel from the capital to that city. The King guarantees that for every city, there exists a travel plan from the capital.

Input

The input is read from the file jump.in.

The first line contains four integers $n, m, w, h$, with meanings as described above.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of city $i$.

The next $m$ lines each contain six integers $p_i, t_i, L_i, R_i, D_i, U_i$, representing the city index where the $i$-th jump device is located, the time required for the jump, and the rectangular range of reachable coordinates, respectively.

Output

The output is written to the file jump.out.

Output $n-1$ lines, where the $i$-th line contains a single integer representing the minimum time required to travel from the capital to city $i+1$.

Examples

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

Output 1

50
50
60
123

Input 2

(See jump/jump2.in)

Output 2

(See jump/jump2.ans)

Note

The constraints for this sample are $n = 10000, m = 20000, w = 10000, h = 1$.

Input 3

(See jump/jump3.in)

Output 3

(See jump/jump3.ans)

Note

The constraints for this sample are $n = 10000, m = 20000, w = 10000, h = 10000$.

Constraints

For all test cases and samples: $1 \le n \le 70000$, $1 \le m \le 150000$, $1 \le w, h \le n$, $1 \le t_i \le 10000$.

The memory limit for this problem is $128\text{MB}$.