아브라카다브라

Tin Golubić, 일명 Mr. Magic Man은 바라주딘에서 가장 재능 있는 젊은 마술사 중 한 명이다. 그의 전문 분야는 카드 마술이다. 이 문제는 여러 해 동안 우리가 목격한 인상적인 마술들에 바치는 헌사이다.

Tin의 마술에는 $N$장의 카드로 이루어진 덱이 쓰인다. 각 카드의 앞면에는 $1$부터 $N$까지의 정수가 하나씩 적혀 있으며, 카드의 총 개수는 짝수이다. Tin은 리플 셔플을 연달아 하는 것처럼 보이게 한다. 관객은 언제든지 이렇게 물을 수 있다. "$t$번 셔플한 뒤 아래에서 $i$번째 카드의 앞면에 적힌 수는 무엇입니까?" Tin은 즉시 정확한 답을 말한다.

이 마술의 비밀은 두 가지다. 첫째, Tin은 덱의 처음 상태를 정확히 기억한다. 처음에 어떤 카드가 어느 위치에 있는지 알고 있다.

둘째, 그의 셔플은 관객이 눈치채지 못하도록 조금 변형된 리플 셔플이다. 일반적인 리플 셔플과 마찬가지로 Tin은 아래쪽 절반의 카드를 왼손에, 위쪽 절반의 카드를 오른손에 든다. 두 손의 카드는 항상 뒷면이 위를 향한다. 그는 카드를 한 장씩 떨어뜨려 탁자 위에 새 덱을 만든다. 어느 손을 쓸지 무작위로 고르지 않는다. 항상 앞면에 적힌 수가 더 작은 쪽의 맨 아래 카드를 떨어뜨린다. 한쪽 손의 카드를 모두 떨어뜨리면, 다른 손에 남은 카드를 모두 한꺼번에 떨어뜨린다. 떨어뜨린 카드를 모으면 셔플이 끝난다.

Tin은 처음 덱에서 시작해 현재 덱을 계속 셔플한다. 각 셔플은 직전 셔플의 결과에 적용된다.

Tin의 마술을 시뮬레이션하는 프로그램을 작성하라. 처음 덱이 주어지면 관객의 $Q$개 질문에 답하라.

첫 줄에는 정수 $N$과 $Q$가 주어진다. $N$은 짝수임이 보장된다.

둘째 줄에는 양의 정수 $N$개가 주어진다. 이 수들은 $\{1,2,\dots,N\}$의 순열이며, 처음 덱의 상태를 아래에서 위 순서로 나타낸다.

이어지는 $Q$개의 줄에는 각각 정수 $t$와 $i$가 주어진다($1 \le i \le N$). $j$번째 줄은 $j$번째 질문이며, $t$번 셔플한 뒤 덱의 아래에서 $i$번째 카드에 적힌 수를 묻는다.

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 질문의 답인 $1$ 이상 $N$ 이하의 정수 하나를 출력한다.

모든 서브태스크에서 $2 \le N \le 200000$, $1 \le Q \le 1000000$, $0 \le t \le 10^9$이다.