Задача C. Современная библиотека ≡

Условие

Группа, состоящая P из юных программистов, поступила на первый курс университета. Занятия на первом курсе будут продолжаться в течение D дней. Помочь студентам в приобретении знаний может новая библиотека университета, в которой имеется B различных книг, посвящённых программированию. Из-за проблем с финансированием каждая книга имеется в единственном экземпляре.

В библиотеке недавно внедрена новая автоматизированная система выдачи книг, поэтому теперь библиотека может выдавать и принимать от одного человека не больше одной книги в день.

Каждый студент, ознакомившись со списком изданий, составил для себя план самообучения, в котором указал, какую книгу в какой день он хочет получить, а в какой — сдать обратно.

Если в день, когда студент пришёл за книгой, она оказалась на руках у другого, то в этот день он ничего не делает и весь его план сдвигается вперёд на один день. В частности, если он собирался в этот день сдать какую-нибудь книгу, то это действие тоже откладывается.

Если несколько студентов приходят в библиотеку в один день, они обслуживаются в порядке списка, составленного при поступлении в университет.

Может оказаться, что найдутся два или более студентов, каждый из которых имеет на руках книгу, нужную в этот момент кому-то другому. В такой ситуации все они будут откладывать своё обучение неограниченно долго, и в конце концов отчислятся из университета. Остальные студенты закончат обучение успешно.

По представленным планам самообучения требуется для каждого студента определить, сколько книг он прочтёт и будет ли отчислен.

Рекомендуется рассмотреть частичные решения

P = 2

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

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

Каждое описание содержит D пар целых чисел R_i, T_i, которые означают что в i-ый день студент хочет сдать книгу с номером R_i и получить книгу с номером T_i. Если студент не собирается брать или сдавать книгу в этот день, соответствующее число равно нулю.

Планы перечислены в порядке, соответствующем порядку обслуживания студентов.

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

Выходной файл должен содержать P пар целых чисел Q_i M_i, где Q_i — количество книг, которые прочитает i-й студент, M_i равно единице, если i-ый студент будет отчислен, и нулю в противном случае.

Ограничения

1 ≤ P, D ≤ 200

1 ≤ B ≤ 10⁵

0 ≤ R_i, T_i ≤ B

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

2 4
0 1  0 2  1 0  2 0
0 2  0 1  1 0  2 0

1 1
1 1

3 4
0 1  0 3  1 0  3 0
0 2  2 3  3 5  5 0
0 3  0 0  3 4  4 0

2 0
3 0
2 0