Disease

Interview

Time limit2sMemory limit512 MB

Summary

Given m tests, each listing which bacteria it checks for and its positive or negative result, classify every bacterium as impossible, certainly present, or undetermined, or report that the results contradict each other.

Level: Medium5 of 10
Topics: Implementation, Brute force, Math, Greedy
Solved: No attempts yet

Problem

An epidemic of a dangerous disease has broken out in Byteland. The disease is caused by $n$ distinct pathogenic bacteria.

To treat a patient correctly, the doctors must know exactly what caused the illness. The patient therefore takes $m$ tests: each test checks for the presence or absence of certain species of bacteria. A test returns a positive result if the patient's blood contains at least one of the pathogens that the test checks for.

Help the doctors determine, from the test results, whether the patient is infected with each bacterium.

Input

The first line of the input file contains two integers $n$ ( $1 \le n \le 100$ ), the number of distinct pathogens, and $m$ , the number of tests. The following $m$ ( $1 \le m \le 10\,000$ ) lines each contain $n + 1$ integers. The first $n$ integers describe which pathogens the test detects: the $i$ -th integer is 1 if the test checks for the presence of the $i$ -th pathogen, and 0 otherwise.

The last integer on the line is 1 if the test returned a positive result, and 0 otherwise.

Output

If the input data are contradictory, print the single line <<Incorrect>> to the output file. Otherwise, print three lines to the output file. Each line is formatted as: the number of bacteria, followed by their indices.

On the first line, print the indices of the bacteria that cannot be the cause of the disease; on the second line, the indices of the bacteria that can be stated with certainty to be the cause of the disease; on the third line, the indices of the bacteria about which nothing can be stated from the test results.

Examples3

Example 1

Input

Expected output

2 1 2
1 3
0

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