[NOI2019] 弹跳

原题时限 2s 内存 128MB

跳蚤国有 $n$ 座城市，分别编号为 $1 - n$，$1$ 号城市为首都。所有城市分布在一个$w \times h$ 范围的网格上。每座城市都有一个整数坐标 $(x, y) (1 \leq x \leq w, 1 \leq y \leq h)$，不同城市的坐标不相同。 在跳蚤国中共有 $m$ 个弹跳装置，分别编号为 $1 - m$，其中 $i$ 号弹跳装置位于 $p_i$ 号城市，并具有参数 $t_i, L_i, R_i, D_i, U_i$。利用该弹跳装置，跳蚤可花费 $t_i (t_i > 0)$ 个单位时间，从 $p_i$ 号城市跳至坐标满足 $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)$ 的任意一座城市。需要注意的是，一座城市中可能存在多个弹跳装置，也可能没有弹跳装置。 由于城市间距离较远，跳蚤们必须依靠弹跳装置出行。具体来说，一次出行将经过 若干座城市，依次经过的城市的编号可用序列 $a_0, a_1, \cdots , a_k$ 表示；在此次出行中，依次利用的弹跳装置的编号可用序列 $b_1, b_2, \cdots , b_k$ 表示。其中每座城市可在序列 $\{a_j\}$ 中出现任意次，每个弹跳装置也可在序列 $\{b_j\}$ 中出现任意次，且满足，对于每个 $j (1 \leq j \leq k)$，编号为 $b_j$ 的弹跳装置位于城市 $a_{j-1}$，且跳蚤能通过该弹跳装置跳至城市 $a_j$。我们称这是一次从城市 $a_0$ 到城市 $a_k$ 的出行，其进行了 $k$ 次弹跳，共花费 $\sum^k_{i=1} t_{b_{i}}$ 个单位时间。 现在跳蚤国王想知道，对于跳蚤国除首都（$1$ 号城市）外的每座城市，从首都出发，到达该城市最少需要花费的单位时间。跳蚤国王保证，对每座城市，均存在从首都到它的出行方案。

第一行包含四个整数 $n, m,w, h$，变量的具体意义见题目描述。 接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i, y_i$，表示 $i$ 号城市的坐标。 接下来 $m$ 行，第 $i$ 行包含六个整数 $p_i, t_i, L_i, R_i, D_i, U_i$，分别表示 $i$ 号弹跳装置所在的城市编号、弹跳所需的时间、可到达的矩形范围。这些整数的具体意义见题目描述。

输出 $n - 1$ 行，第 $i$ 行包含一个整数，表示从跳蚤国首都到 $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

### 更多样例 您可以通过附加文件获得更多样例。 #### 样例 2 见附加文件中的 `jump/jump2.in` 与 `jump/jump2.ans`。 这组样例的数据范围为 $n = 10^4 , m = 2\times 10^4 , w = 10^4 , h = 1$。 #### 样例 3 见附加文件中的 `jump/jump3.in` 与 `jump/jump3.ans`。 这组样例的数据范围为 $n = 10^4 , m = 2\times 10^4 , w = 10^4 , h = 10^4$。 ### 数据范围 对于所有测试点和样例满足： $1 \leq n \leq 70000 , 1 \leq m \leq 150000 , 1 \leq w, h \leq n , 1 \leq t_i \leq 10000$。 每个测试点的具体限制见下表。 | 测试点编号 | $1\le n\le$ | $1\le m\le$ | 特殊限制 | | :----------: | :----------: | :----------: | :----------: | | $1\sim8$ | $100$ | $100$ | 无 | | $9\sim13$ | $5\times 10^4$ | $10^5$ | 每个弹跳装置恰好可达一座城市，且 $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$ | 无 | | $23\sim25$ | $7\times 10^4$ | $1.5\times 10^5$ | 无 |