Dragon Curve

Time limit1sMemory limit512 MB

Summary

Generate the segments of N dragon curves on a 101 by 101 grid, mark the grid points they pass through, and count unit squares whose four corners are all marked.

Level: Medium6 of 10
Topics: Implementation, Recursion, Simulation, Math
Solved: No attempts yet

Problem

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.

Starting point
Starting direction
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.

Input

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 (↓)

Output

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

Hint



Example with 3 dragon curves	Example with 4 dragon curves

Examples4

Example 1
Input
```
3
3 3 0 1
4 2 1 3
4 2 2 1
```
Expected output
```
4
```
Example 2
Input
```
4
3 3 0 1
4 2 1 3
4 2 2 1
2 7 3 4
```
Expected output
```
11
```

Example 3

Input

Expected output

Example 4

Input

Expected output