409455: GYM103566 C Посудомойка

C. Посудомойкаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный выводЯ женщина, а не посудомойка!

Алина учится на отлично, участвует в олимпиадах, занимается спортом. К сожалению, это никак не спасает её от $$$\textit{«Дочь, помой посуду, пожалуйста!»}$$$

Вчера у мамы Алины был день рождения, на котором гости подарили набор из $$$n$$$ тарелок. Каждая тарелка имеет свой уникальный красивый рисунок и отличается от остальных. Для простоты будем считать, что тарелки занумерованы числами $$$1, 2, \ldots, n$$$.

Сегодня утром Алина увидела, что после вчерашней встречи никто не помыл посуду, поэтому $$$n$$$ грязных подаренных тарелок разложены в $$$k$$$ стопок на кухне. Известно, что сегодня к маме снова придут гости, а Алине придётся помогать их обслуживать. В течение дня у мамы будет $$$q$$$ просьб двух видов:

1. $$$\textit{«Дай, пожалуйста, тарелку i»}$$$  — в дальнейшем будем обозначать такую просьбу $$$1\ i$$$.

   На эту просьбу Алине надо будет поставить на праздничный стол тарелку c номером $$$i$$$. В этот момент тарелка $$$i$$$ должна быть $$$\textbf{чистой}$$$.

2. $$$\textit{«Убери, пожалуйста, тарелку i»}$$$  — в дальнейшем будем обозначать такую просьбу $$$2\ i$$$.

   На эту просьбу Алине надо будет убрать со стола тарелку с номером $$$i$$$ в одну из $$$k$$$ стопок. Cчитаем, что в этот момент тарелка $$$i$$$ была использована и стала $$$\textbf{грязной}$$$. Тарелку можно убрать только $$$\textbf{наверх}$$$ стопки.

Понятно, что для того, чтобы выполнить просьбу типа $$$1$$$, тарелку $$$i$$$ необходимо в какой-то момент $$$\textbf{помыть}$$$. Опишем процесс мытья посуды подробнее:

• Алина может взять тарелку сверху из какой-то стопки и помыть её.
• Брать тарелку из середины стопки нельзя — по неосторожности можно случайно уронить стопку и разбить посуду (мама будет очень недовольна).
• Нельзя перекладывать тарелку из стопки в стопку — если мама увидит это, то вставит неуместный комментарий про неэффективность Алины в таком простом деле, как мытьё посуды.
• Помытую тарелку Алина складывает в шкаф с чистой посудой. Шкаф может вместить единовременно все $$$n$$$ чистых тарелок.

Алина очень хочет как можно больше времени посвятить саморазвитию. Она просит помочь $$$\textbf{минимизировать количество помытых в процессе тарелок}$$$. Каждый случай мытья тарелки учитывается в ответе отдельно.

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

Входные данные

В первой строке записаны 3 целых числа $$$n$$$, $$$k$$$, $$$q$$$ ($$$1 \le n, k, q \le 10^5$$$) — количество тарелок, количество стопок с посудой, количество просьб мамы соответственно.

В следующих $$$k$$$ строках идёт описание стопок. В строке $$$r + 1$$$ описывается стопка с номером $$$r$$$. Первое число в строке $$$s_r$$$ — количество тарелок в стопке $$$r$$$. Далее идут $$$s_r$$$ чисел — номера тарелок, лежащих в стопке (в порядке снизу вверх, то есть последнее число — номер тарелки, лежащей сверху стопки).

Гарантируется, что:

• $$$s_1 + s_2 + \dots + s_k = n$$$  — все тарелки лежат в стопках грязной посуды.
• все тарелки во всех стопках различны  — каждая тарелка лежит ровно в одной стопке ровно в одном экземпляре.

Далее следуют $$$q$$$ просьб мамы, в следующем формате: $$$t\ i$$$ ($$$1\le t \le 2, 1 \le i \le n$$$).

• $$$t$$$ — тип просьбы (1 — поставить тарелку на стол, 2 — убрать тарелку со стола);
• $$$i$$$ — номер тарелки, с которой надо провести действие.

Гарантируется, что просьбы мамы $$$\textbf{не противоречивы}$$$, то есть не бывает такого, что мама просит поставить на стол тарелку, которая уже там стоит или убрать со стола тарелку, которой на нём нет.

Выходные данные

В первой строке выведите $$$a$$$  — минимальное количество помытых в процессе тарелок. Каждый случай мытья тарелки учитывается в ответе отдельно.

В следующих $$$a + q$$$ строках выведите действия Алины. Каждое действие в следующем формате:

• $$$1$$$ — поставить на стол чистую тарелку. В этот момент первая невыполненная просьба мамы должна быть вида $$$(1, i)$$$, а тарелка $$$i$$$ должна находиться в шкафу с чистой посудой.
• $$$2 \ j$$$ ($$$1 \le j \le k$$$) — взять со стола грязную тарелку $$$i$$$ и положить её наверх стопки с номером $$$j$$$. В этот момент первая невыполненная просьба мамы должна быть вида $$$(2, i)$$$.
• $$$3 \ j$$$ ($$$1 \le j \le k$$$) — взять из стопки с номером $$$j$$$ верхнюю тарелку (в этот момент стопка $$$j$$$ должна содержать в себе хотя бы одну тарелку), помыть её и убрать в шкаф с чистой посудой.

В последовательности действий должно быть ровно $$$a$$$ действий 3-го типа.

Если существует несколько оптимальных последовательностей действий Алины  — выведите любую из них.

ПримерВходные данные

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

Выходные данные

3
3 2
3 2
1
1
2 3
3 1
1

Примечание

Опишем действия в примере:

1. Хотим поставить тарелку номер $$$1$$$ на стол, чтобы выполнить первую просьбу мамы, но не можем этого сделать, потому что тарелка $$$1$$$ не лежит на вершине стопки. Поэтому сначала моем и убираем в шкаф тарелку номер $$$3$$$ из $$$2$$$-й стопки.
2. Тарелка номер $$$1$$$ лежит на вершине $$$2$$$-й стопки, моем её и убираем в шкаф.
3. Из шкафа выставляем чистую тарелку номер $$$1$$$ на стол.
4. Затем хотим выставить на стол тарелку номер $$$3$$$. Она уже лежит в шкафу, поэтому можем сразу её выставить.
5. Надо убрать тарелку номер $$$1$$$ со стола. Положим её в стопку номер $$$3$$$. Аналогично можно было положить в пустую стопку номер $$$2$$$.

   (Неоптимально убирать тарелку в стопку номер $$$1$$$  — в дальнейшем нам понадобится тарелка номер $$$2$$$ из той стопки, но тарелка номер $$$1$$$ «перекроет» к ней доступ).

6. Далее надо выставить на стол тарелку номер $$$2$$$, но она грязная. Поэтому помоем её и уберём в шкаф.
7. Теперь выставляем чистую $$$2$$$-ю тарелку на стол.