이상한 안테나

대통령이 나라 전체를 관측하려고 한다. 국토는 $n \times n$ 크기의 격자로 나뉘어 있고, 각 칸의 꼭짓점이 격자점이 된다. 격자점의 행 번호와 열 번호는 모두 $0$부터 $n$까지이다. 대통령은 어느 격자점에나 안테나를 세울 수 있다.

안테나는 남동, 남서, 북동, 북서 가운데 한 방향으로 신호를 보낸다. 신호가 닿는 영역은 직각이등변삼각형이다. 직각인 꼭짓점은 안테나가 선 격자점이고, 길이가 같은 두 변은 각각 신호 방향의 세로 성분과 가로 성분을 따라 뻗으며, 그 길이는 안테나의 출력 $p$와 같다. 예를 들어 남동 방향 안테나의 두 변은 안테나에서 남쪽과 동쪽으로 뻗는다.

한 칸은 이 삼각형과 겹치는 부분의 넓이가 $0$보다 클 때 그 신호가 덮은 칸으로 센다. 꼭짓점이나 변에서만 닿으면 덮은 것이 아니다.

이 안테나는 이상하다. 한 칸에서 두 신호가 겹치면 서로 상쇄된다. 그래서 어떤 칸은 그 칸을 덮는 신호의 개수가 홀수일 때만 관측된다.

이미 세워 둔 안테나 $a$개가 주어질 때, 관측되는 칸이 몇 개인지 구하여라.

$n = 10$이고 안테나가 둘인 경우를 보자. 안테나 X는 행 $0$, 열 $0$에 서서 출력 $4$의 신호를 남동으로 보내고, 안테나 Y는 행 $1$, 열 $5$에 서서 출력 $4$의 신호를 남서로 보낸다.

x x x x - - - - - -
x o o y y - - - - -
x x y y y - - - - -
x - - y y - - - - -
- - - - y - - - - -
- - - - - - - - - -
- - - - - - - - - -
- - - - - - - - - -
- - - - - - - - - -
- - - - - - - - - -

x는 X만 덮은 칸, y는 Y만 덮은 칸, o는 두 신호가 겹쳐 상쇄된 칸이다. 관측되는 칸은 모두 16개다.

첫째 줄에 격자의 한 변에 놓인 칸의 수 $n$이 주어진다. 둘째 줄에 안테나의 개수 $a$가 주어진다. 이어지는 $a$개의 줄에는 안테나마다 행 위치, 열 위치, 출력 $p$, 방향이 공백으로 구분되어 주어진다. 방향은 $0$이면 남서, $1$이면 남동, $2$이면 북동, $3$이면 북서다.

$0 < n \le 30000$, $0 \le a \le 100$, $0 < p \le 2n$이고, 행 위치와 열 위치는 $0$ 이상 $n$ 이하의 정수다.

관측되는 칸의 개수를 한 줄에 출력한다.