Бэтмен — успешный миллиардер, бизнесмен и супергерой. Для сохранения порядка в городе ему необходимо использовать все чудеса современной техники.
Для создания гаджетов используют самые современные технологии. Завод по производству техники состоит из n конвейеров и m этапов производства. На каждом этапе производства предметы остаются на своем месте либо переходят на один из конвейеров, причем в каждый момент времени на одном конвейере находится ровно один предмет.
Изначально на всех m этапах предметы не меняются местами, то есть после прохождения этапа все предметы остаются на своем месте.
Со временем технологии меняются и необходимо перестраивать завод.
Существуют два типа запросов:
В первой строке заданы числа 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