Strange Antennas

Problem

The president wants to survey the whole country. The territory is a grid of $n \times n$ cells, and every corner of a cell is a grid point. Rows and columns of grid points are numbered from $0$ to $n$ . The president can install an antenna at any grid point.

An antenna sends a signal in one of four directions: south-east, south-west, north-east, north-west. The signal covers an isosceles right triangle. Its right angle sits at the grid point of the antenna, and the two equal sides run along the vertical component and the horizontal component of that direction, each with a length equal to the power $p$ of the antenna. The two sides of a south-east antenna, for example, run south and east from the antenna.

A cell counts as covered by a signal when the triangle overlaps it in a region of positive area. Touching only at a corner or along an edge is not coverage.

These antennas are strange. When two signals overlap in a cell, they cancel each other. A cell is surveyed only when the number of signals covering it is odd.

Given the $a$ antennas that are already installed, count the surveyed cells.

Consider $n = 10$ with two antennas. Antenna X stands at row $0$ , column $0$ and sends a signal of power $4$ to the south-east. Antenna Y stands at row $1$ , column $5$ and sends a signal of power $4$ to the south-west.

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

Here x is a cell covered by X only, y is a cell covered by Y only, and o is a cell where the two signals cancel. 16 cells are surveyed.

Input

The first line contains $n$ , the number of cells along one side of the grid. The second line contains $a$ , the number of antennas. Each of the next $a$ lines contains the row position, the column position, the power $p$ , and the direction of one antenna, separated by spaces. The direction is $0$ for south-west, $1$ for south-east, $2$ for north-east, $3$ for north-west.

$0 < n \le 30000$ , $0 \le a \le 100$ , $0 < p \le 2n$ , and the row and column positions are integers between $0$ and $n$ .

Output

Print the number of surveyed cells on one line.