There are cities in Byteland numbered from to and city is the capital. All cities's location are on a grid, which has an integer coordinate . Different cities share different locations.
There are portals in Byteland numbered from to . Portal is located at city , with some constraints . With portal , Kevin can spend transporting from to a city where its location satisfies . One city may have many portals.
Starting from city , Kevin wants to know the least time needed to go to every city . Note that Kevin can only transport with portals and only using portals take time. It is guaranteed that there is at least a way to go to each city from city .
The first line contains four integers .
In the following lines, each line contains two integers , indicating the coordinate of city .
In the following lines, each line contains six integers , indicating constraints of portal .
For all test cases, .
|Test Case||Additional Constraints|
|9~13||Every portal can reach exactly 1 city, and|
In line , output the answer to city .
Sample Input 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
Sample Output 1
50 50 60 123