P5471 [NOI2019] Jumping

The original time limit is 2 s. The memory limit is 128 MB.

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.

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

### 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. | Test Point ID | $1\le n\le$ | $1\le m\le$ | Special Constraints | | :----------: | :----------: | :----------: | :----------: | | $1\sim8$ | $100$ | $100$ | None | | $9\sim13$ | $5\times 10^4$ | $10^5$ | Each jumping device can reach exactly one city, and $L_i=R_i$, $D_i=U_i$ | | $14\sim18$ | $5\times 10^4$ | $10^5$ | $h=1$ | | $19\sim22$ | $2.5\times 10^4$ | $5\times 10^4$ | None | | $23\sim25$ | $7\times 10^4$ | $1.5\times 10^5$ | None | Translated by ChatGPT 5