Завод

시간 제한2초메모리 제한1024 MB

요약

각 단계가 두 컨베이어 자리를 맞바꾸는 m개의 단계 배열에서, 갱신과 함께 시작 자리를 처음 x개 단계에 통과시킨 결과를 구한다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 분할 정복, 배열, 구현
정답자: 아직 제출이 없습니다

문제

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

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

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

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

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

$a, b, x$ --- Пусть после этапа $x$ предмет с конвейера $a$ попадает на $A$ , а с $b$ на $B$ . Тогда после применения запроса $A$ и $B$ меняются местам, то есть предмет с конвейера $a$ попадает на $B$ , а с $b$ на $A$ .
$r, x$ --- Вам необходимо узнать на каком конвейере окажется предмет после этапа $x$ , если изначально он находился на конвейере $r$ .

입력

В первой строке заданы числа $n$ , $m$ и $q$ --- количество конвейеров, этапов и запросов ( $1 \le n, m, q \le 10^5$ ).

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

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

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

출력

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

예제2

예제 1
입력
```
3 4 4
1 3 4
0 3 2 2
1 3 2
1 2 4
```
예상 출력
```
3
2
3
```
예제 2
입력
```
3 3 3
0 1 2 1
0 2 3 2
1 1 3
```
예상 출력
```
3
```