16007번 - Shootings 서브태스크다국어

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.

The standard input contains on the first line a natural number N representing the number of target rectangles. On each of the following N lines, there are 4 natural numbers defining a target rectangle, X₁, Y₁, X₂, Y₂, 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 representing the number of shootings. On the following T lines, there are two integers P 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).

The standard 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 file. Again, for each determined cost, you must display the square of its value.

• 1 ≤ N ≤ 50000
• 1 ≤ T ≤ 100000
• 1 ≤ X₁ < X₂ ≤ 100000, 1 ≤ Y₁ < Y₂ ≤ 100000
• -100000 ≤ P ≤ 200000
• 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 can be squares
• the rectangles have nonzero area
• there can be identical shootings
• note that the numbers from the output file are always non-negative integers

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

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