Undergraduate Researcher Minsang

Interview

Time limit1sMemory limit512 MB

Summary

Count the cells reached by wind from all air conditioners on a grid where four object types redirect the wind.

Level: Medium5 of 10
Topics: BFS, Simulation, Implementation
Solved: No attempts yet

Problem

Minsang has just joined the lab as an undergraduate researcher and is choosing where to sit.

The lab is a grid, and air conditioners blow wind in four directions: up, down, left, and right. Wind also blows in the cell containing an air conditioner.

Minsang gets hot easily, so he will pick one of the cells that the air conditioner wind passes through.

The lab has various objects that change the direction of the wind.

There are four types of objects. The arrows in the table below show how the wind moves at each object.


Object type	Object shape	Wind movement direction
Object 1
Object 2
Object 3
Object 4

Minsang can sit in any cell in the lab. That is, he can sit in a cell with an air conditioner and in a cell with an object.

Count how many seats Minsang wants.

Input

The first line gives the vertical size $N(1 \le N \le 2,000)$ and the horizontal size $M(1 \le M \le 2,000)$ of the lab, in that order.

From the second line through the $(N+1)$ -th line, $M$ values describing the lab's interior are given on each line.

$1, 2, 3, 4$ are the object types described above. $9$ denotes an air conditioner, and $0$ denotes an empty cell.

There are between $0$ and $50$ air conditioners.

Output

Print the number of seats Minsang wants.

Examples5

Example 1

Input

8 8
0 0 0 0 0 0 0 0
0 0 0 3 0 0 0 4
0 1 0 0 3 0 0 3
0 0 0 0 0 0 1 0
0 1 0 9 0 0 4 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0

Expected output

Example 2

Input

Expected output

Example 3
Input
```
3 3
3 0 4
0 9 0
4 0 3
```
Expected output
```
5
```
Example 4
Input
```
3 5
9 0 0 0 4
4 0 0 0 0
0 0 0 0 3
```
Expected output
```
15
```
Example 5
Input
```
4 4
1 0 1 0
0 2 0 2
3 0 3 0
0 4 0 4
```
Expected output
```
0
```