32165번 - 잊음을 논함

정수 $N$개로 구성된 수열 $a$가 있으며, 초기에 모든 $i$에 대해 $a_i=i$이다. 여러분은 이 수열에 대해 다음과 같은 질의를 $Q$개 처리해야 한다.

• s $i$ $j$: $a_i$와 $a_j$를 서로 교환한다.
• f $i$: 지금까지 입력된 질의 중 $i$번째 질의를 잊는다. $i$번째 질의는 s 질의였으며, 잊지 않은 상태임이 보장된다.
• r $i$: 지금까지 입력된 질의 중 $i$번째 질의를 다시 기억해 낸다. $i$번째 질의는 s 질의였으며, 잊은 상태임이 보장된다.
• q $i$: 지금까지 입력된 s 질의 중 잊지 않은 상태인 것만을 순서대로 반영했을 때, $a_i$의 값을 출력한다.

이때 s 질의의 잊은 여부는 다음과 같이 정의된다.

• 모든 s 질의는 매 시점 잊은 상태 또는 잊지 않은 상태 중 하나에 해당한다.
• s 질의가 주어진 직후 이 s 질의는 잊지 않은 상태가 된다.
• 잊지 않은 상태인 s 질의를 잊으면 이 s 질의는 잊은 상태가 된다.
• 잊은 상태인 s 질의를 다시 기억해 내면 이 s 질의는 잊지 않은 상태가 된다.

잊는 것은 병이 아니다. 잊지 않는 것이 병이 아닌 것은 아니다. 여러분은 잊어야 할 것을 잊을 수 있을까?

첫 번째 줄에 수열의 길이 $N$과 질의의 개수 $Q$가 주어진다. ($2 \le N \le 4\,000\,000$; $1 \le Q \le 2\,000\,000$)

두 번째 줄부터 $Q$개의 줄에 걸쳐 지문에 주어진 대로 질의가 한 줄에 하나씩 주어진다.

모든 s 질의에 대해 $1 \le i<j \le N$이며, 모든 q 질의에 대해 $1 \le i \le N$이다.

모든 입력에서 q 질의는 적어도 하나 주어진다.

각 q 질의에 대해 정답을 한 줄에 하나씩 출력한다.