Origami is the traditional Japanese art of paper folding. One day, Professor Egami found the message board decorated with some pieces of origami works pinned on it, and became interested in the pinholes on the origami paper. Your mission is to simulate paper folding and pin punching on the folded sheet, and calculate the number of pinholes on the original sheet when unfolded.
A sequence of folding instructions for a ﬂat and square piece of paper and a single pinhole position are speciﬁed. As a folding instruction, two points P and Q are given. The paper should be folded so that P touches Q from above (Figure 4). To make a fold, we ﬁrst divide the sheet into two segments by creasing the sheet along the folding line, i.e., the perpendicular bisector of the line segment PQ, and then turn over the segment containing P onto the other. You can ignore the thickness of the paper.
The original ﬂat square piece of paper is folded into a structure consisting of layered paper segments, which are connected by linear hinges. For each instruction, we fold one or more paper segments along the speciﬁed folding line, dividing the original segments into new smaller ones. The folding operation turns over some of the paper segments (not only the new smaller segments but also some other segments that have no intersection with the folding line) to the reﬂective position against the folding line. That is, for a paper segment that intersects with the folding line, one of the two new segments made by dividing the original is turned over; for a paper segment that does not intersect with the folding line, the whole segment is simply turned over.
The folding operation is carried out repeatedly applying the following rules, until we have no segment to turn over.
Rule 1: The uppermost segment that contains P must be turned over.
Rule 2: If a hinge of a segment is moved to the other side of the folding line by the operation, any segment that shares the same hinge must be turned over.
Rule 3: If two paper segments overlap and the lower segment is turned over, the upper segment must be turned over too.
In the examples shown in Figure 5, (a) and (c) show cases where only Rule 1 is applied. (b) shows a case where Rule 1 and 2 are applied to turn over two paper segments connected by a hinge, and (d) shows a case where Rule 1, 3 and 2 are applied to turn over three paper segments.
After processing all the folding instructions, the pinhole goes through all the layered segments of paper at that position. In the case of Figure 6, there are three pinholes on the unfolded sheet of paper.