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 .

#### Input Specification

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 .

#### Constraints

For all test cases, .

Test Case | Additional Constraints | ||
---|---|---|---|

1~8 | None | ||

9~13 | Every portal can reach exactly 1 city, and | ||

14~18 | |||

19~22 | None | ||

23~25 |

#### Output Specification

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
```

## Comments