1부터 N까지의 숫자가 적혀있는 카드 더미가 있다. 이때 N은 항상 짝수이다. 더미의 가장 아래는 첫번째 숫자 카드가 있고, 가장 위에는 마지막 숫자 카드가 위치해 있도록 순서대로 배치되어 있다.

한번의 "셔플"이란, 카드 더미의 중앙을 기준으로 분리한 뒤, 가장 아래 있는 카드에 적혀있는 수 두 개를 비교하여 더 작은 카드를 내려놓는 방식으로 진행된다.

예를 들어, "1 5 6 2 3 4"를 분리하면 "1 5 6"과 "2 3 4"가 되고, 작은 카드부터 내려놓게되면 "1 2 3 4 5 6"이 된다.

총 Q개의 쿼리를 처리하는데, i번 쿼리는 셔플을 ai번 진행한 뒤 bi번 위치에 있는 카드의 번호를 구하는 것이다.

각 쿼리에 대한 답을 구하시오.

셔플 timer 1s memory 1024MB

셔플 1s 1024MB