학원 수업이 끝날 무렵, 선생님은 오늘의 숙제 양을 사다리타기로 정하겠다고 선언했다. 칠판에는 세로줄 개가 왼쪽부터 번으로 그려져 있다. 각 세로줄의 아래 끝에는 그 줄에 도착한 학생이 해야 할 숙제의 양이 적혀 있다.
처음에는 가로줄이 하나도 없다. 선생님은 이웃한 두 세로줄 번과 번을 높이 에서 잇는 가로줄을 하나씩 추가한다. 높이는 위에서부터 잰 값이므로, 가 작을수록 위쪽에 있다. 한 번 추가한 가로줄은 사라지지 않는다.
사다리는 다음과 같이 탄다. 세로줄의 맨 위에서 출발하여 아래로 내려간다. 현재 세로줄에 연결된 가로줄을 만나면 반드시 그 가로줄을 따라 반대편 세로줄로 건너간 뒤, 그 높이보다 아래로 계속 내려간다. 더 이상 만나는 가로줄이 없으면 현재 세로줄의 아래 끝에 도착한다.
예를 들어, 높이 에 번과 번 세로줄을 잇는 가로줄이 있고, 높이 에 번과 번 세로줄을 잇는 가로줄이 있다고 하자. 번 세로줄에서 출발하면 높이 에서 번으로 건너가고, 높이 에서 번으로 건너가므로 번 세로줄에 도착한다.
데자뷰는 선생님이 가로줄을 추가하는 도중에도 현재 사다리에서 어느 세로줄에 도착하는지 알고 싶다. 다음 두 종류의 쿼리 개를 주어진 순서대로 처리하여라.
한 세로줄에 같은 높이의 가로줄이 두 개 이상 연결되는 경우는 없다. 서로 연결되는 세로줄이 겹치지 않는다면 여러 가로줄이 같은 높이에 있을 수 있다.
입력은 다음과 같은 형식으로 주어진다.
각 번 쿼리에 대해 도착하는 세로줄의 번호를 한 줄에 출력한다. 테스트 케이스가 입력된 순서대로, 각 테스트 케이스 안에서는 쿼리가 주어진 순서대로 출력한다. 번 쿼리가 없는 테스트 케이스에서는 아무것도 출력하지 않는다.
처음 두 번의 쿼리에서는 모두 높이 의 가로줄을 따라 번에서 번으로 건너간다. 두 번째 쿼리에서는 높이 의 가로줄도 있지만, 그 높이를 지날 때에는 번 세로줄에 있으므로 만나지 않는다.
첫째 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
각 테스트 케이스의 첫째 줄에 세로줄의 개수 과 쿼리의 개수 가 공백으로 구분되어 주어진다. 다음 개의 줄에는 쿼리가 처리할 순서대로 주어지며, 각 줄은 또는 형식이다. 각 테스트 케이스는 서로 독립적이며, 처음에는 가로줄이 하나도 없다.
마지막 가로줄까지 추가하면 높이 에 , 높이 에 , 높이 에 를 잇는 가로줄이 있다. 이때 번에서 출발하면 로 이동하여 번에 도착한다. 번에서 출발하면 높이 에서 번으로 건너가고, 그대로 번에 도착한다.
첫 번째 테스트 케이스에서는 가로줄을 추가하기 전에는 번에, 추가한 뒤에는 번에 도착한다.
두 번째 테스트 케이스에는 번 쿼리가 없으므로 출력할 내용이 없다.
세 번째 테스트 케이스는 가로줄이 없는 새로운 사다리에서 시작한다. 따라서 각각 출발한 세로줄인 번과 번에 도착한다.
처음 추가하는 두 가로줄은 높이가 모두 이지만, 각각 와 를 이어 서로 세로줄을 공유하지 않으므로 허용된다.
높이 에 추가한 가로줄은 먼저 추가한 두 가로줄보다 위쪽에 있다. 이 가로줄을 추가한 직후 번에서 출발하면 로, 번에서 출발하면 로 이동한다.
마지막으로 높이 의 가로줄을 추가하면 번에서 출발한 경로는 번에서 번으로 한 번 더 건너간다.
