Flea Kingdom: Shortest Travel Time

Flea Kingdom has \(n\) cities, numbered from \(1\) to \(n\), located on a \(w \times h\) grid. City \(1\) is the capital. Each city has a unique integer coordinate \((x,y)\) satisfying \(1 \le x \le w\) and \(1 \le y \le h\).

There are \(m\) jump devices, numbered from \(1\) to \(m\). The \(i\)-th device is located in city \(p_i\) and has parameters \(t_i, L_i, R_i, D_i, U_i\). Using the \(i\)-th jump device, a flea can jump from city \(p_i\) to any city whose coordinate \((x,y)\) satisfies \(L_i \le x \le R_i\) and \(D_i \le y \le U_i\) (with \(1 \le L_i \le R_i \le w\) and \(1 \le D_i \le U_i \le h\)). The jump takes \(t_i\) units of time (with \(t_i > 0\)).

A travel from one city to another is accomplished by a sequence of jumps. That is, if a flea travels through cities \(a_0,a_1,\ldots,a_k\) using jump devices \(b_1,b_2,\ldots,b_k\) respectively, then for every \(j\) with \(1 \le j \le k\), the device \(b_j\) is located in city \(a_{j-1}\) and can jump to city \(a_j\). The total time cost is \(\sum_{j=1}^k t_{b_j}\).

The king of Flea Kingdom wants to know, for every city except the capital (city \(1\)), the minimum time required to travel from the capital to that city. It is guaranteed that every city is reachable from the capital.

inputFormat

The first line contains four integers \(n, m, w, h\) representing the number of cities, the number of jump devices, and the dimensions of the grid.

The next \(n\) lines each contain two integers \(x\) and \(y\), representing the coordinates of city \(i\) (\(1 \leq i \leq n\)). City \(1\) is the capital.

The following \(m\) lines each contain six integers \(p_i, t_i, L_i, R_i, D_i, U_i\), describing the \(i\)-th jump device. Here, \(p_i\) is the city where the device is located, \(t_i\) is the time cost, and \(L_i, R_i, D_i, U_i\) specify the rectangular region of destination cities.

outputFormat

Output \(n-1\) lines. The \(i\)-th line (for \(2 \le i \le n\)) should contain a single integer representing the minimum total time required to travel from the capital (city \(1\)) to city \(i\).

sample

3 2 5 5
1 1
3 3
5 5
1 2 2 5 2 5
2 3 4 5 4 5

2
2