Since he has began military training for some time, and has not received any vacation yet, Mihai has decided to try his luck once again with his superior, Captain Dan. Dan was somewhat more kind this time, but first he asked him to prove his talent as a shooter.

We can imagine the targets in the firing range as rectangles in the plane. The Captain tells Mihai some points on the OX axis and directions in which to shoot. Each shot is a half-line that can be oriented either diagonally left at 45^o, diagonally right at 45^o, or vertically.

We define a shot’s cost of hitting a target as the length of the intersection of the shot’s half-line with the target rectangle. If the intersection is either the empty set or consists of a single point, then the cost is 0.

We define the cost of a shot as the sum of the shot’s costs of hitting all the targets. Determine each shot’s cost.

Input

The input contains on the first line a natural number N (1 ≤ N ≤ 50000) representing the number of target rectangles. On each of the following N lines, there are 4 natural numbers defining a target rectangle, X1, Y1, X2, Y2 (1 ≤ X1 < X2 ≤ 100000, 1 ≤ Y1 < Y2 ≤ 100000), separated by spaces and representing the coordinates of the lower-left and upper-right corners respectively. On the next line there is a natural number T (1 ≤ T ≤ 100000) representing the number of shootings. On the following T lines, there are two integers P (-100000 ≤ P ≤ 200000) and D separated by a space representing the X coordinate of the point from which Mihai shoots and the direction of the shooting (D = 1 signifies a vertical shot, D = 2 signifies a diagonally left oriented shot and D = 3 sign a diagonally right oriented shot).

All rectangle sides are parallel with OX and OY axis. No two rectangles intersect (i.e. have common points) and there is no rectangle completely included into another rectangle. The rectangles have nonzero area, and can be squares. There can be identical shootings. The numbers from the output are always non-negative integers.

Output

The output contains T lines, each having a nonegative integer representing the square cost of a shot, in the order in which they appear in the input. Again, for each determined cost, you must display the square of its value.

Constraints

Time limit: 1 second
Memory limit: 128 megabytes

Examples

input
4
1 1 4 3
2 4 5 7
6 3 10 5
8 1 9 2
2
0 3
9 1

output
18
9

The cost of the first shot is (2√2 + √2)²=18
The cost of the second shot is (1 + 2)²=9