Задача G. Катание на лифте ≡

Условие

Однажды k учеников решили прогулять школу и покататься на лифте. Для этого они направились в дом с самым большим в городе лифтом.

Катание на лифте проходило следующим образом: школьники одновременно нажимали на случайные кнопки этажей (несколько школьников могли нажать на одну и ту же кнопку). При этом срабатывала одна из нажатых кнопок, после чего лифт всегда ехал либо вверх, либо вниз на соответствующий этаж. Далее операция повторялась.

После n-го раза лифт приехал на какой-то этаж и сломался — не открыл двери. Школьники помнят, какие кнопки были ими нажаты перед каждой поездкой и в каком направлении при этом перемещался лифт (вверх или вниз). Для вызова диспетчера необходимо узнать, на каких этажах может находиться лифт. Помогите им это выяснить. Известно, что сначала лифт стоял на первом этаже.

Формат входного файла

Первая строка входного файла содержит целые числа n k — количество поездок на лифте и количество школьников соответственно.

Следующие n строк содержат k + 1 чисел каждая: d_i f_1,i… f_k,i — направление движения лифта и номера этажей, кнопки которых были нажаты. Этажи нумеруются с 1.

• Если d_i равно 1, то после одновременного нажатия на кнопки этажей f_1,i, …, f_k,i лифт поехал вверх, на один из этих этажей.
• Если d_i равно  − 1 — лифт поехал вниз.

Формат выходного файла

Выходной файл должен содержать последовательность целых чисел — номеров этажей, на которых может находится сломанный лифт, упорядоченную по возрастанию.

Если данные школьников противоречивы (т. е. хотя бы одна из описанных поездок невозможна), выходной файл должен содержать единственное число  − 1.

Ограничения

1 ≤ n, k ≤ 100, 1 ≤ f_i,j ≤ 1000

Примеры тестов

4 4
 1  4 8 5 7
 1  3 6 9 3
 1  1 2 4 4
-1  1 2 1 4

-1

3 4
 1  4 8 5 4
-1  6 9 6 4
-1  3 8 5 6

3 5

2 2
1  1 1
1  1 2

-1