Description

There are $n$ cities in Flea Kingdom, numbered from $1$ to $n$, and city $1$ is the capital. All cities are located on a grid within a $w \times h$ area. Each city has integer coordinates $(x, y) (1 \leq x \leq w, 1 \leq y \leq h)$, and no two cities share the same coordinates.

There are $m$ jumping devices in Flea Kingdom, numbered from $1$ to $m$. Device $i$ is located in city $p_i$ and has parameters $t_i, L_i, R_i, D_i, U_i$. By using this device, a flea can spend $t_i (t_i > 0)$ units of time to jump from city $p_i$ to any city whose coordinates satisfy $L_i \leq x \leq R_i, D_i \leq y \leq U_i (1 \leq L_i \leq R_i \leq w, 1 \leq D_i \leq U_i \leq h)$. Note that a city may have multiple jumping devices, or none.

Because cities are far apart, fleas must rely on jumping devices to travel. Specifically, a trip will pass through several cities; the city numbers in order can be written as a sequence $a_0, a_1, \cdots , a_k$. The jumping device numbers used in order can be written as a sequence $b_1, b_2, \cdots , b_k$. Each city may appear in the sequence $\{a_j\}$ any number of times, and each jumping device may appear in the sequence $\{b_j\}$ any number of times. For each $j (1 \leq j \leq k)$, device $b_j$ is located in city $a_{j-1}$, and the flea can use this device to jump to city $a_j$. We call this a trip from city $a_0$ to city $a_k$. It makes $k$ jumps in total, and costs $\sum^k_{i=1} t_{b_{i}}$ units of time.

Now the flea king wants to know, for every city other than the capital (city $1$), the minimum number of time units needed to start from the capital and reach that city. The king guarantees that for every city, there exists at least one trip from the capital to it.

Input Format

The first line contains four integers $n, m, w, h$. The meanings of the variables are described in the statement.

The next $n$ lines: line $i$ contains two integers $x_i, y_i$, indicating the coordinates of city $i$.

The next $m$ lines: line $i$ contains six integers $p_i, t_i, L_i, R_i, D_i, U_i$, indicating the city where device $i$ is located, the time needed for the jump, and the reachable rectangular region. The meanings of these integers are described in the statement.

Output Format

Output $n - 1$ lines. Line $i$ contains one integer, representing the minimum number of time units needed to travel from the capital of Flea Kingdom to city $i + 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

50
50
60
123

Hint

More Samples

You can obtain more samples through the additional files.

Sample 2

See jump/jump2.in and jump/jump2.ans in the additional files.

The Constraints for this sample are $n = 10^4 , m = 2\times 10^4 , w = 10^4 , h = 1$.

Sample 3

See jump/jump3.in and jump/jump3.ans in the additional files.

The Constraints for this sample are $n = 10^4 , m = 2\times 10^4 , w = 10^4 , h = 10^4$.

Constraints

For all test points and samples:

$1 \leq n \leq 70000 , 1 \leq m \leq 150000 , 1 \leq w, h \leq n , 1 \leq t_i \leq 10000$.

The detailed limits for each test point are shown in the table below.

Translated by ChatGPT 5