Автор: | Анна Малова (Жюри XXI командной олимпиады школьников Санкт-Петербурга по информатике и программированию) | Ограничение времени: | 2 сек | |
Входной файл: | disease.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | disease.out |
В Байтландии вспыхнула эпидемия опасной болезни. Известно, что возбудителями болезни являются n различных болезнетворных бактерий.
Для правильного лечения пациента врачам необходимо знать, чем именно была вызвана его болезнь. Для этого пациент сдает m анализов: каждый анализ проверяет наличие или отсутствие некоторых видов бактерий. Анализ дает положительный результат, если в крови у человека есть хотя бы один из проверяемых этим анализом возбудителей болезни.
Помогите врачам по результатам анализов выяснить про каждую бактерию, заражен ли ею пациент.
В первой строке входного файла заданы два числа n (1 ≤ n ≤ 100) — число различных возбудителей болезни и m — число анализов. Следующие m (1 ≤ m ≤ 10 000) строк содержат по n + 1 числу. Первые n чисел описывают, какие возбудители обнаруживаются этим анализом, i-е число равно 1, если анализ проверяет наличие i-го возбудителя и 0 — в противном случае.
Последнее число в строке равно 1, если анализ дал положительный результат, и 0 — в противном случае.
Если входные данные противоречивы, выведите в выходной файл единственную строку Incorrect. В противном случае выведите в выходной файл три строки. Каждая строка задается в формате: число бактерий, далее их номера.
В первой строке необходимо вывести номера бактерий, которые не могут являться причиной болезни, во второй — номера бактерий, про которые можно точно утверждать, что они являются причиной болезни, в третьей — номера бактерий, про которые по результатам анализов ничего утверждать нельзя.
№ | Входной файл (disease.in ) |
Выходной файл (disease.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|