Завод
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
conveyor.in
вывод
conveyor.out

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

Для создания гаджетов используют самые современные технологии. Завод по производству техники состоит из n конвейеров и m этапов производства. На каждом этапе производства предметы остаются на своем месте либо переходят на один из конвейеров, причем в каждый момент времени на одном конвейере находится ровно один предмет.

Изначально на всех m этапах предметы не меняются местами, то есть после прохождения этапа все предметы остаются на своем месте.

Со временем технологии меняются и необходимо перестраивать завод.

Существуют два типа запросов:

  1. a, b, x — Пусть после этапа x предмет с конвейера a попадает на A, а с b на B. Тогда после применения запроса A и B меняются местам, то есть предмет с конвейера a попадает на B, а с b на A.

  2. r, x  — Вам необходимо узнать на каком конвейере окажется предмет после этапа x, если изначально он находился на конвейере r.

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

В первой строке заданы числа n, m и q — количество конвейеров, этапов и запросов (1 ≤ n, m, q ≤ 105).

Каждая из следующих q строк начинается с целого числа t — тип очередного запроса (0 ≤ t ≤ 1). При t = 0 запрос первого типа, иначе второго.

Далее в запросах первого типа следует тройка целых чисел a, b и x (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ x ≤ m).

В запросах второго типа следуют целые числа r и x (1 ≤ r ≤ n, 1 ≤ x ≤ m).

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

Для каждого запроса второго типа выведите результат в отдельной строке.

Система оценки

Первая группа тестов состоит из тестов, для которых выполняются ограничения n, m, q ≤ 100. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 12 баллов.

Вторая группа тестов состоит из тестов, для которых выполняются ограничения m, q ≤ 5000. Баллы за эту группу начисляются только при прохождении всех тестов группы и всех предыдущих групп. Стоимость группы составляет 14 баллов.

Третья группа тестов состоит из тестов, для которых выполняются ограничения n = 2. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 25 баллов.

Четвертая группа тестов состоит из тестов, для которых выполняются ограничения n, m, q ≤ 25000. Баллы за эту группу начисляются только при прохождении всех тестов группы и всех предыдущих групп. Стоимость группы составляет 30 баллов.

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

Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Request feedback» на вкладке «Runs».

Примеры

Входные данные
3 4 4
1 3 4
0 3 2 2
1 3 2
1 2 4
Выходные данные
3
2
3
Входные данные
3 3 3
0 1 2 1
0 2 3 2
1 1 3
Выходные данные
3