D. Разведение магических существ
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Никита и Саша играют в компьютерную игру, в которой нужно разводить магических существ. Изначально у них есть k существ, занумерованных числами от 1 до k. У существ есть n различных характеристик.

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

Они применяют свои заклинания и интересуются некоторыми характеристиками своих новых существ. Помогите им узнать эти характеристики.

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

В первой строке содержатся числа n, k и q (1 ≤ n ≤ 105, 1 ≤ k ≤ 12, 1 ≤ q ≤ 105) — количество характеристик, существ и запросов.

Следующие k строк описывают изначальных существ. Строка i содержит n чисел ai1, ai2, ..., ain (1 ≤ aij ≤ 109) — характеристики существа i.

Следующие q строк содержат описания запросов. Строка i содержит числа ti, xi и yi (1 ≤ ti ≤ 3). Они означают следующее:

  • Если ti = 1, это означает, что Саша применил своё заклинание к существам с номерами xi и yi.
  • Если ti = 2, это означает, что Никита применил своё заклинание к существам с номерами xi и yi.
  • Если ti = 3, это означает, что они решили узнать, чему у существа под номером xi равна характеристика под номером yi. В этом случае 1 ≤ yi ≤ n.

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

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

На каждый запрос с ti = 3 выведите соответствующую характеристику.

Примеры
Входные данные
2 2 4
1 2
2 1
1 1 2
2 1 2
3 3 1
3 4 2
Выходные данные
2
1
Входные данные
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
Примечание

В первом примере Саша создаёт существо под номером 3 с характеристиками (2, 2). Никита создаёт существо под номером 4 и с характеристиками (1, 1). После этого они узнают первую характеристику у существа 3 и вторую характеристику у существа 4.