#1845. [NOI 2019] Jump

[NOI 2019] Jump

Description

There are nn cities in the Kingdom of Flea, numbered from 11 to nn, and city 11 is the capital. All of the cities are located in a grid graph of size w×hw \times h. Each city has an integer coordinate (x,y)(1xw,1yh)(x, y)\,(1 \leq x \leq w, 1 \leq y \leq h), and the coordinates of the cities are different from each other.

There are mm bouncing devices in the Kingdom of Flea, numbered from 11 to mm. The ii-th device is located in city pip_i and with this device, a flea in city pip_i can jump to any city that satisfies LixRiL_i \leq x \leq R_i, DiyUiD_i \leq y \leq U_i in tit_i time units.

Since that the cities are quite far away from each other, so fleas always travel by the bouncing devices. Specifically, during a trip a flea will pass through several cities in turn, whose indices are a0,a1,,aka_0, a_1, \cdots, a_k, respectively; in this trip, the indices of bouncing devices used in turn are b1,b2,,bkb_1, b_2, \cdots, b_k. Each cities can appear any number of times in the sequence {aj}\{a_j\}, and each bouncing devices can appear any number of times in the sequence {bj}\{b_j\} and for each j(1jk)j\, (1 \leq j \leq k), bouncing devices bjb_j is located in the city aj1a_{j−1} and the flea can jump to city aja_j with the help of the bouncer. We call this a trip from city a0a_0 to city aka_k, which costs i=1ktbi\sum_{i=1}^{k}{t_{b_i}} time units.

Now the Flea King wants to know that for every city except the capital of the kingdom (city 11), how much time it will at least take to get to the city from the capital.

Input

The first line contains 44 integers n,m,w,hn, m, w, h.

Each of the next nn lines contains 22 integers xi,yix_i, y_i.

Each of the next mm lines contains 66 integers pi,ti,Li,Ri,Di,Uip_i, t_i, L_i, R_i, D_i, U_i, describing the information of the ii-th bouncing device.

It's guaranteed that every city is reachable from the capital.

Output

You should print n1n - 1 lines, the ii-th line contains the minimum time it needs to get to city i+1i + 1 from the capital.

Sample

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

Limits And Hints

  • 1n700001 \leq n \leq 70000
  • 1m1500001 \leq m \leq 150000
  • 1w,hn1 \leq w, h \leq n
  • 1ti100001 \leq t_i \leq 10000

Partial scores are listed below.

测试点编号 1n1\le n\le 1m1\le m\le Additional Constraints
181\sim 8 100100 100100 No
9139\sim 13 5×1045\times 10^4 10510^5 Every bouncing devices can reach exactly
one city, and Li=Ri,L_i = R_i, Di=UiD_i = U_i
141814\sim 18 5×1045\times 10^4 10510^5 h=1h=1
192219\sim 22 2.5×1042.5\times 10^4 5×1045\times 10^4 No
232523\sim 25 7×1047\times 10^4 1.5×1051.5\times 10^5 No

Please note that the memory limit of this problem is 128 MB.