시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)4201109530.159%

문제

지환이는 업무에 치여 산다. 하루에도 몇 건인지도 모를 정도로 많은 업무가 들어온다.

각 업무는 양의 정수로 표현되는 고유번호 $p_i$ ($1 \leq p_i \leq N$)를 가지고 있으며, 고유번호는 모두 다르다.

아, 일이 또 추가되었다. 참다못한 지환이는 스케줄링을 하기 위한 기계 ‘지환봇 스케줄러’를 만들었지만, 그마저도 제대로 만들지는 못한 것 같다. '지환봇 스케줄러'는 기본적으로는 스택(stack) 구조, 즉 제일 나중에 들어간 업무가 제일 먼저 처리되는(LIFO, Last in First out) 특성을 가지고 있다.

기본적인 특성과 더불어, '지환봇 스케줄러'에게 할 수 있는 명령은 다음과 같다.

  • $0\ p$: 고유번호가 $p$인 업무를 스케줄러에 추가한다. 특별히 다른 명령이 없는 한, 새로 추가된 일은 스케줄러 상의 맨 앞에 추가된다. 즉, 고유번호 값에 상관없이 스케줄러에서 가장 먼저 처리되어야 하는 업무가 된다.
  • $1$: 스케줄러에 들어있는 업무를 고유번호 값 기준으로 오름차순으로 정렬한다. 이 결과, 고유번호 값이 낮은 업무일수록 스케줄러의 앞에 배치된다.
  • $2$: 스케줄러에 있는 업무 처리 순서를 뒤집는다. 즉, 스케줄러에 들어가 있는 업무들의 처리 순서가 반대가 된다.

'지환봇 스케줄러'에 필요 없어 보이는 기능이 있는 것 같지만, 지환이는 이전보다 효과적인 업무처리를 기대할 수 있을 것 같다. 주어진 $Q$개의 명령을 순서대로 처리한 후, $k$번째로 처리해야 하는 업무의 고유번호는 무엇일까?

입력

첫째 줄에 업무의 고유번호의 범위 제한 $N$과 명령 횟수 $Q$, $k$가 주어진다. ($1\leq N,Q \leq 100\,000,\ 1\leq k \leq$ '0번 명령의 등장 횟수')

둘째 줄부터 $Q$개 줄에 걸쳐 명령에 대한 정보가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

모든 명령을 순서대로 적용한 후, $k$번째로 처리하게 될 업무의 고유번호를 출력한다.

예제 입력 1

5 7 5
0 1
0 2
0 3
1
0 4
0 5
2

예제 출력 1

5