Никита и Саша играют в компьютерную игру, в которой нужно разводить магических существ. Изначально у них есть k существ, занумерованных числами от 1 до k. У существ есть n различных характеристик.
У Саши есть заклинание, позволяющее по двум существам создать новое. Каждая его характеристика будет равна максимуму из соответствующих характеристик использованных существ. У Никиты есть похожее заклинание, но в этом случае каждая характеристика нового существа равна минимуму из соответствующих характеристик использованных существ. Новое существо получает минимальный свободный номер. При этом существа можно использовать в заклинаниях несколько раз.
Они применяют свои заклинания и интересуются некоторыми характеристиками своих новых существ. Помогите им узнать эти характеристики.
Выходные данные
На каждый запрос с ti = 3 выведите соответствующую характеристику.
Примечание
В первом примере Саша создаёт существо под номером 3 с характеристиками (2, 2). Никита создаёт существо под номером 4 и с характеристиками (1, 1). После этого они узнают первую характеристику у существа 3 и вторую характеристику у существа 4.
| № | Входные данные | Выходные данные |
|
1
|
2 2 4
1 2
2 1
1 1 2
2 1 2
3 3 1
3 4 2
|
2
1
|
|
2
|
5 3 8
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
1 1 2
1 2 3
2 4 5
3 6 1
3 6 2
3 6 3
3 6 4
3 6 5
|
5
2
2
3
4
|