G. LaLa and Divination Magic
time limit per test
4 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$\color{blue}{\text{LaLa}}$$$ specializes in divination $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$.

Let's say there are $$$M$$$ events $$$E_0, \cdots, E_{M-1}$$$ that $$$\color{blue}{\text{LaLa}}$$$'s interested in forecasting. Each event is associated with one of two outcomes: catastrophe or salvation.

With a single use of $$$\color{blue}{\text{LaLa}}$$$'s divination $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$, $$$\color{blue}{\text{LaLa}}$$$ obtains the knowledge of one of the following four forms:

  1. $$$\mathrm{Knowledge}(i,j,1)$$$: either $$$E_i$$$ is catastrophe or $$$E_j$$$ is catastrophe (possibly both).
  2. $$$\mathrm{Knowledge}(i,j,2)$$$: either $$$E_i$$$ is salvation or $$$E_j$$$ is catastrophe (possibly both).
  3. $$$\mathrm{Knowledge}(i,j,3)$$$: either $$$E_i$$$ is catastrophe or $$$E_j$$$ is salvation (possibly both).
  4. $$$\mathrm{Knowledge}(i,j,4)$$$: either $$$E_i$$$ is salvation or $$$E_j$$$ is salvation (possibly both).

$$$\color{blue}{\text{LaLa}}$$$ cast her $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ several times, possibly 0, and wrote down all $$$M$$$-tuples of the outcomes of events that are consistent with her knowledge: this is called the result of the forecasting. And then, $$$\color{blue}{\text{LaLa}}$$$ fell asleep.

When $$$\color{blue}{\text{LaLa}}$$$ woke up, she found out that her pet, $$$\color{brown}{\text{Leo}}$$$, ruined all the predictions of her $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$. Though $$$\color{blue}{\text{LaLa}}$$$ was able to find the result of her forecasting, she is unsure if that data was ruined by $$$\color{brown}{\text{Leo}}$$$ as well.

Write a program that determines whether there exists a set of predictions of $$$\color{blue}{\text{LaLa}}$$$'s $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ whose result of the forecasting matches the one $$$\color{blue}{\text{LaLa}}$$$ has, and finds a possible set of predictions if there is one.

Input

The input is given in the following format:

$$$N$$$$$$M$$$
$$$S_0$$$
$$$S_1$$$
$$$\vdots$$$
$$$S_{N-1}$$$

where $$$N$$$ is the number of outcomes in the result, $$$M$$$ of events, and $$$S_i$$$ is a binary string of length $$$M$$$ where $$$j$$$-th character is '1' if and only if the $$$i$$$-th result forecasts that $$$j$$$-th event will be in salvation.

The input satisfies the following constraints:

  • $$$N$$$ and $$$M$$$ are integers.
  • $$$1 \le N, M \le 2\,000$$$
  • $$$S_i \ne S_j$$$ for all integers $$$0 \le i \lt j \lt N$$$.
Output

If there is no such prediction, the output should be a single integer $$$-1$$$.

Otherwise, the output should be in the following format:

$$$K$$$
$$$I_0$$$$$$J_0$$$$$$t_0$$$
$$$I_1$$$$$$J_1$$$$$$t_1$$$
$$$\vdots$$$
$$$I_{K-1}$$$$$$J_{K-1}$$$$$$t_{K-1}$$$

where $$$K$$$ is the size of a possible set $$$S$$$ of predictions, and, for each $$$0 \le i \lt K$$$, $$$S$$$ contains the prediction $$$\mathrm{Knowledge}(I_i,J_i,t_i)$$$.

The output should satisfy the following constraint:

  • $$$0 \le K \le 2\cdot M^2$$$

It can be proved that if there is such a set of predictions, there also is one satisfying the constraint.

Examples
Input
2 1
1
0
Output
0
Input
3 3
101
011
111
Output
6
0 2 3
0 1 4
0 2 4
1 2 3
1 2 4
2 2 4