You are optimizing a map application, which is targeted at Icpca City.
The area of Icpca City has a square shape, which is divided into square sections of the same size lined up in $$$n$$$ rows and $$$n$$$ columns. The section located at the $$$i$$$-th row and the $$$j$$$-th column ($$$1 \leq i \leq n$$$, $$$1 \leq j \leq n$$$) is denoted by $$$(i, j)$$$. For example, the section at the northwest corner is denoted by $$$(1, 1)$$$. Icpca City has its central station occupying a single section, and some number of buildings occupying rectangular areas of one or more sections.
Your map application can calculate the shortest walking time between two specified sections. In the calculation, we assume that people can walk to one of the sections adjacent to north, south, east, and west in $$$1$$$ minute, and they cannot move diagonally. In addition, we assume that people cannot enter sections occupied by buildings nor step outside of Icpca City. However, they can enter the section of the central station.
During the test phase, you noticed that users frequently ask the walking time from the central station. Write an efficient program that processes many user queries asking for the shortest walking time from the central station to specified sections.
Figure F.1 is a sketch of Icpca City of the first test case of Sample Input 1, showing the shortest path from the central station to the section $$$(1, 7)$$$. The central station, the section $$$(1, 7)$$$, and buildings are shown in green, cyan stripe, and dark gray, respectively. The shortest walking time is $$$17$$$ minutes.
 |
| Figure F.1: The first test case of Sample Input 1 |
The input contains one or more test cases, each in the following format.
| $$$n$$$ $$$u$$$ $$$v$$$ |
| $$$m$$$ |
| $$$a_1$$$ $$$b_1$$$ $$$c_1$$$ $$$d_1$$$ |
| $$$a_2$$$ $$$b_2$$$ $$$c_2$$$ $$$d_2$$$ |
| $$$\vdots$$$ |
| $$$a_m$$$ $$$b_m$$$ $$$c_m$$$ $$$d_m$$$ |
| $$$q$$$ |
| $$$s_1$$$ $$$t_1$$$ |
| $$$s_2$$$ $$$t_2$$$ |
| $$$\vdots$$$ |
| $$$s_q$$$ $$$t_q$$$ |
The first line consists of three integers, $$$n, u,$$$ and $$$v$$$ $$$(2 \leq n \leq 10^9, 1 \leq u \leq n, 1 \leq v \leq n)$$$, which mean that the number of sections on each side is $$$n$$$, and that the central station is located at the section $$$(u, v)$$$.
The second line contains an integer $$$m$$$ $$$(1 \leq m \leq 200)$$$, representing the number of buildings in Icpca City. The next $$$m$$$ lines contain information regarding the areas of the buildings. The $$$i$$$-th line of these $$$m$$$ lines consists of four integers, $$$a_i, b_i, c_i,$$$ and $$$d_i$$$ $$$(1 \leq a_i \leq b_i \leq n, 1 \leq c_i \leq d_i \leq n)$$$, which mean the $$$i$$$-th building occupies all sections $$$(x, y)$$$ that meets $$$a_i \leq x \leq b_i$$$ and $$$c_i \leq y \leq d_i$$$. It is guaranteed that no sections are occupied by two or more buildings, and the section of the central station is not occupied by any buildings.
The next line contains an integer $$$q$$$ $$$(1 \leq q \leq 2 \times 10^5)$$$, which is the number of queries. The next $$$q$$$ lines contain information regarding the user queries. The $$$j$$$-th line of these $$$q$$$ lines consists of two integers, $$$s_j$$$ and $$$t_j$$$ $$$(1 \leq s_j \leq n, 1 \leq t_j \leq n)$$$, which describe the query to calculate the shortest walking time from the central station to the section $$$(s_j, t_j)$$$. It is guaranteed that the section $$$(s_j, t_j)$$$ is not occupied by any buildings.
The end of the input is indicated by a line containing three zeros. The number of test cases does not exceed $$$200$$$. The sum of $$$m$$$ over all the test cases does not exceed $$$200$$$, and the sum of $$$q$$$ over all the test cases does not exceed $$$2 \times 10^5$$$.
For each test case, output $$$q$$$ lines. In the $$$j$$$-th line $$$(1 \leq j \leq q)$$$, output the answer to the $$$j$$$-th query in minutes. If the specified section is unreachable, output no as the answer.
7 6 123 7 3 31 4 5 641 75 56 26 110 1 145 6 4 45 6 7 74 4 5 67 7 5 6310 103 35 62 1 121 1 2 22 2 1 112 29 1 142 2 1 84 4 2 96 6 1 88 8 2 931 55 59 910000000 7777777 12345611000001 9000000 1000001 900000032525252 987654310000000 5252525123456 1234560 0 0
17 11 1 0 18 4 no no 4 24 48 17450060 7351292 7654321
