드래곤 커브

드래곤 커브는 다음 세 가지 값으로 정해지고, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향이고, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 길이가 1인 선분 하나다. 아래 그림은 $(0, 0)$에서 시작하고 시작 방향이 오른쪽인 0세대 드래곤 커브다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점 기준으로 시계 방향으로 90도 회전시킨 다음, 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점은 시작 점에서 선분을 따라 이동했을 때 가장 멀리 떨어진 점이다.

2세대 드래곤 커브도 1세대를 만든 방법을 그대로 써서 만든다. 파란색 선분이 새로 붙인 선분이다.

3세대 드래곤 커브는 2세대 드래곤 커브로 만든다. 아래 그림이 3세대 드래곤 커브다.

즉, $K$세대 드래곤 커브($K > 1$)는 $K-1$세대 드래곤 커브를 끝 점 기준으로 시계 방향으로 90도 회전시킨 다음 그 끝 점에 붙인 것이다.

크기가 $100 \times 100$인 격자 위에 드래곤 커브가 $N$개 있다. 네 꼭짓점이 모두 드래곤 커브의 일부인 크기 $1 \times 1$ 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 $(x, y)$로 나타내고, $0 \le x \le 100$과 $0 \le y \le 100$을 만족하는 좌표만 유효하다.

첫째 줄에 드래곤 커브의 개수 $N$ ($1 \le N \le 20$)이 주어진다. 둘째 줄부터 $N$개의 줄에 드래곤 커브의 정보가 네 정수 $x$, $y$, $d$, $g$로 주어진다. $x$와 $y$는 드래곤 커브의 시작 점, $d$는 시작 방향, $g$는 세대다. ($0 \le x, y \le 100$, $0 \le d \le 3$, $0 \le g \le 10$)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향 $d$는 0, 1, 2, 3 중 하나이고 다음을 뜻한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

첫째 줄에 네 꼭짓점이 모두 드래곤 커브의 일부인 크기 $1 \times 1$ 정사각형의 개수를 출력한다.