There is a square piece of paper. The vertices of the paper are in 2D Cartesian coordinates. In other words, it is a square paper with side length . There are folding operations.
Each folding operation can be described using two points and . You will fold the current piece of work along the line determined by and , and the portion to the right of the vector should be folded to the left. Note that the whole line through the points, not just the segment, is folded. See the explanation for the sample input if you are not yet familiar with the notions of left and right.
Now you are given points. You need to compute, for each point , the number of layers of paper at that point in the end.
For additional guarantees satisfied by the input, see the Constraints section.
Input Specification
The first line consists of an integer denoting the number of folds.
In the following lines, each line has four floating point numbers with at most 4 digits after the decimal point describing each fold.
Next, there is a positive integer denoting the number of query points.
In the following lines, each line consists of two floating point numbers with at most 4 digits after the decimal point denoting a query point.
Output Specification
For each query, output a line with an integer denoting the number of layers of paper at point .
Sample Input
2
100 0.0 0 100
50 50 0 50
5
75 75.0
10 80
20.0000 40
20 10
70 10
Sample Output
0
0
4
2
2
Explanation
You start with a piece of paper with vertices .
In the first fold, you will fold along the main diagonal of the paper. Now the paper is folded into two layers: the paper is now a triangle with vertices . The lightly shaded orange area represents the area that is folded to the left
In the second fold, you will fold along the line : you will fold the portion above it down. After that, the shape of the paper will be a trapezoid with vertices . Furthermore, over the triangle bounded by , there are 4 layers, while in the rest of the paper there are 2 layers. In the below diagram, the lightly shaded orange area represents the region that is folded left/down, the dark shaded blue regions represent the part where there are 4 layers, and lightly shaded blue regions represent the part where there are 2 layers.
Constraints
For all test cases, . For all fold lines where and , we have . For all query points , we have . All floating point numbers in the input have at most 4 digits after the decimal point.
Furthermore, the test data generated satisfy the following constraints:
- The minimum area of any layer is at least .
- When viewed as a simple polygon (no vertices in the middle of boundaries), each layer has side lengths at least .
- The distance between a query point and the boundary of a layer is at least .
It is possible that the boundary of a layer is contained in the line to be folded.
Scoring
- Subtask 1 (5 points): .
- Subtask 2 (21 points): .
- Subtask 3 (14 points): .
- Subtask 4 (30 points): all folds are parallel to the -axis or the -axis.
- Subtask 5 (30 points): no additional constraints. Depends on all previous subtasks.
Comments