Cube pile

Interview

Time limit1sMemory limit1024 MB

Summary

Count the cubes whose six face-adjacent positions all contain cubes in an N by N by N grid.

Level: Easy2 of 10
Topics: Implementation, Array
Solved: No attempts yet

Problem

A cube space of size $N \times N \times N$ is given. A coordinate in this space is a triple of integers $(i,j,k)$ satisfying $1 \leq i,j,k \leq N$ .

There are $M$ cubes in the space, and each cube occupies exactly one coordinate. No two cubes share a coordinate. Count the cubes that satisfy the following condition.

If a cube exists at $(i,j,k)$ , then cubes also exist at all 6 positions $(i\pm1,j,k), (i,j\pm1,k), (i,j,k\pm1)$ .

Input

The first line contains two integers $N$ and $M$ .

Each of the next $M$ lines contains three integers $i$ , $j$ , and $k$ . This means a cube exists at $(i,j,k)$ .

Output

Print the answer to the problem.

Constraints

$3 \leq N \leq 5$
$0 \leq M \leq N^3$
$1 \leq i,j,k \leq N$
No coordinate is given more than once

Examples2

Example 1
Input
```
3 1
1 1 1
```
Expected output
```
0
```

Example 2

Input

Expected output