Dragon Curve

A dragon curve is fixed by three values and it is defined on the two dimensional coordinate plane. On that plane the x axis runs in the → direction and the y axis runs in the ↓ direction.

1. Starting point
2. Starting direction
3. Generation

A generation 0 dragon curve is a single segment of length 1. The figure below is the generation 0 dragon curve that starts at $(0, 0)$ with the starting direction to the right.

The generation 1 dragon curve is the generation 0 curve turned 90 degrees clockwise about its end point and then attached to the end point of the generation 0 curve. The end point is the point that lies farthest away when you travel from the starting point along the segments.

The generation 2 dragon curve is built from generation 1 by the same method. The blue segments are the ones just attached.

The generation 3 dragon curve is built from the generation 2 curve. The figure below is the generation 3 dragon curve.

In other words, the generation $K$ dragon curve ($K > 1$) is the generation $K-1$ curve turned 90 degrees clockwise about its end point and attached to that end point.

A grid of size $100 \times 100$ holds $N$ dragon curves. Write a program that counts the squares of size $1 \times 1$ whose four corners all belong to a dragon curve. A grid coordinate is written $(x, y)$, and only the coordinates with $0 \le x \le 100$ and $0 \le y \le 100$ are valid.

The first line has the number of dragon curves $N$ ($1 \le N \le 20$). Each of the next $N$ lines describes one dragon curve with four integers $x$, $y$, $d$, $g$. Here $x$ and $y$ are the starting point, $d$ is the starting direction, and $g$ is the generation. ($0 \le x, y \le 100$, $0 \le d \le 3$, $0 \le g \le 10$)

No dragon curve given in the input leaves the grid. Dragon curves can overlap each other.

The direction $d$ is one of 0, 1, 2, 3 and means the following.

• 0: the direction in which the x coordinate increases (→)
• 1: the direction in which the y coordinate decreases (↑)
• 2: the direction in which the x coordinate decreases (←)
• 3: the direction in which the y coordinate increases (↓)

Print on the first line the number of squares of size $1 \times 1$ whose four corners all belong to a dragon curve.