10E. L-Toggle Table

2500 pts1s256 MB

You are given a binary table with $n$ rows and $m$ columns.

In one operation, you choose one L-shaped tile and toggle all cells covered by it.
Toggling a cell means changing $0$ to $1$ and changing $1$ to $0$ .

Each tile covers exactly three cells. The tile is described by the coordinate of its center cell and one of the following four types.

If the center is $(x,y)$ :

Type	Covered cells
$1$	$(x,y)$ , $(x+1,y)$ , $(x,y+1)$
$2$	$(x,y)$ , $(x+1,y)$ , $(x,y-1)$
$3$	$(x,y)$ , $(x-1,y)$ , $(x,y+1)$
$4$	$(x,y)$ , $(x-1,y)$ , $(x,y-1)$

All covered cells must be inside the table.

Your task is to make all cells equal to $0$ using at most $4nm$ operations.

It can be proven that under the given constraints, such a sequence of operations always exists.

Constraints

$2 \le n,m \le 100$
Each cell of the table is either $0$ or $1$

Input

\begin{array}{l} n \quad m \\ s_1 \\ s_2 \\ \vdots \\ s_n \end{array}

Here $s_i$ is a binary string of length $m$ , describing row $i$ of the table.

Output

First, output an integer $k$ , the number of operations.

Then output $k$ lines. Each line must contain three integers $x$ , $y$ , and $p$ , meaning that you apply a tile with center $(x,y)$ and type $p$ .

For every operation, the following must hold:

$1 \le x \le n$
$1 \le y \le m$
$1 \le p \le 4$

Also, all cells covered by the chosen tile must be inside the table.

\begin{array}{l} k \\ \left. \begin{array}{l} x \quad y \quad p \end{array} \right\} \times k \end{array}

Your output must satisfy $0 \le k \le 4nm$ .

If there are multiple valid answers, you may output any of them.

Samples

Input

2 3
101
010

Explanation

Each operation toggles one valid L-shaped tile. After all listed operations, the whole table becomes zero.

Output

Input

Explanation

Initially, the table is:

\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{array}

After applying operation $(2,2,1)$ , cells $(2,2)$ , $(3,2)$ , and $(2,3)$ are toggled. The table becomes:

\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{array}

After applying operation $(2,2,4)$ , cells $(2,2)$ , $(1,2)$ , and $(2,1)$ are toggled. The table becomes:

\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}

So the output is valid.

Output

2
2 2 1
2 2 4

You are given a binary table with $n$ rows and $m$ columns.

In one operation, you choose one L-shaped tile and toggle all cells covered by it.
Toggling a cell means changing $0$ to $1$ and changing $1$ to $0$ .

Each tile covers exactly three cells. The tile is described by the coordinate of its center cell and one of the following four types.

If the center is $(x,y)$ :

Type	Covered cells
$1$	$(x,y)$ , $(x+1,y)$ , $(x,y+1)$
$2$	$(x,y)$ , $(x+1,y)$ , $(x,y-1)$
$3$	$(x,y)$ , $(x-1,y)$ , $(x,y+1)$
$4$	$(x,y)$ , $(x-1,y)$ , $(x,y-1)$

All covered cells must be inside the table.

Your task is to make all cells equal to $0$ using at most $4nm$ operations.

It can be proven that under the given constraints, such a sequence of operations always exists.

$2 \le n,m \le 100$
Each cell of the table is either $0$ or $1$

\begin{array}{l} n \quad m \\ s_1 \\ s_2 \\ \vdots \\ s_n \end{array}

Here $s_i$ is a binary string of length $m$ , describing row $i$ of the table.

First, output an integer $k$ , the number of operations.

Then output $k$ lines. Each line must contain three integers $x$ , $y$ , and $p$ , meaning that you apply a tile with center $(x,y)$ and type $p$ .

For every operation, the following must hold:

$1 \le x \le n$
$1 \le y \le m$
$1 \le p \le 4$

Also, all cells covered by the chosen tile must be inside the table.

\begin{array}{l} k \\ \left. \begin{array}{l} x \quad y \quad p \end{array} \right\} \times k \end{array}

Your output must satisfy $0 \le k \le 4nm$ .

If there are multiple valid answers, you may output any of them.

Initially, the table is:

\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{array}

After applying operation $(2,2,1)$ , cells $(2,2)$ , $(3,2)$ , and $(2,3)$ are toggled. The table becomes:

\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{array}

After applying operation $(2,2,4)$ , cells $(2,2)$ , $(1,2)$ , and $(2,1)$ are toggled. The table becomes:

\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}

So the output is valid.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

10E. L-Toggle Table

Constraints

Input

Output

Samples

10E. L-Toggle Table

Constraints

Input

Output

Samples