Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1866

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Origami is the old Japanese art of folding single sheets of paper into the forms of animals, flowers and other figures. Recently a programmable machine was constructed to make some of the simpler kinds of origami. This machine has a large board with coordinate system drawn on it. First, a square sheet of paper is placed on the board so that the lower left corner has coordinates (0, 0) and the upper right corner has coordinates (100, 100). Then the machine follows the program. The program consists of several steps. Each step is given as a line in the coordinate system at which the origami is to be folded. The line is represented by two points: the paper is folded from right to left when one is facing the second point from the first. The paper on the left side of the line remains in place and the paper on the right side is folded flat on top of it. After the execution of the last step one gets a resulting origami. It is necessary to pierce the origami in order make a hole for hanging. It is important to choose the place for making a hole carefully, because if the origami is too thick in this place it is difficult to make a hole, and if it is too thin it is not strong enough for hanging. Your task is to write a program that computes the number of layers of a paper in the given point.


The first part of the input file contains a program for the origami machine. The first line contains the number of steps of the program. One line follows for each step of the program. Each line contains fold-line coordinates x1 , y1 , x2 , y2 (real numbers) separated by spaces. The program consists of at most 8 steps. The second part of the input file contains several potential points for making a hole. The first line contains the number of such places and each of the next lines contains coordinates of the point.

Input contains multiple test cases. Process to the end of file.


For each of the potential points write a line containing the number of layers pierced through in this point. Note: Assume that the paper has zero thickness and therefore folds ideally. The pierced hole is a single point. The layers pierced exactly at the border of the paper or at the folded edge (within 0.000001) do not count as pierced layers.

Separate output for subsequent test cases with a single blank line.

Sample Input

-0.5 -0.5 1 1
1 75 0 75
10 60
80 60
30 40
10 10
50 50
20 50

Sample Output


Source: University of Waterloo Local Contest 1999.10.02
Submit    Status