애벌레 야시

야시는 나무 위에 살기로 마음먹은 작은 애벌레입니다. 야시가 이사 온 순간, 그가 고른 나무는 아주 어려서 정점이 $1$번 하나뿐입니다.

그 뒤로 나무와 야시는 각자 자기 일을 합니다.

• 나무는 한 번에 하나씩 새 정점을 내며 자랍니다. D x 사건은 이미 나무에 있는 정점 $x$에 새 정점 하나가 붙어 나무에 추가된다는 뜻입니다.
• 야시는 나무 위를 돌아다니며, 매번 지금 있는 정점에서 바로 이웃한 정점 하나로 한 칸 이동합니다. J x 사건은 야시가 정점 $x$가 있는 방향으로 한 칸 움직인다는 뜻입니다. 야시가 실제로 도착한 정점이 아니라, 그가 향하는 목표 정점만 주어진다는 점에 유의하세요.

새로 붙는 정점에는 자연수 번호가 차례로 매겨집니다. 처음 추가된 정점은 $2$번, 그다음은 $3$번, 이런 식입니다. 야시는 항상 $1$번 정점에서 출발합니다.

헥토르는 이 모든 과정을 지켜보면서, 야시가 한 번 움직일 때마다 그가 지금 어디에 있는지 알고 싶어 합니다. 도와줄 수 있나요?

첫 줄에는 테스트 세트의 수를 나타내는 정수 $Z$ ($1 \le Z \le 10$)가 주어집니다. 이어서 각 테스트 세트가 차례로 주어집니다.

각 테스트 세트의 첫 줄에는 사건의 수를 나타내는 정수 $N$ ($1 \le N \le 10^6$)이 주어집니다. 다음 $N$개의 줄에는 각각 사건 하나가 다음 두 형태 중 하나로 주어집니다.

• D x (여기서 $1 \le x \le$ 현재 나무의 정점 개수): 정점 $x$에 새 정점 하나를 붙입니다.
• J x (여기서 $1 \le x \le$ 현재 나무의 정점 개수): 야시가 정점 $x$ 방향으로 한 칸 이동합니다.

J x 사건이 들어온 순간 야시가 이미 정점 $x$에 있다면, 그는 그 자리에 그대로 머무릅니다. 이렇게 위치가 바뀌지 않은 경우에도 그 위치를 반드시 출력해야 합니다.

각 테스트 세트에 대해, J x 사건이 나온 순서대로 사건마다 한 줄씩 출력합니다. 각 줄에는 그 이동 직후 야시가 도착한 정점의 번호를 출력합니다.

예제를 살펴봅시다. 먼저 나무가 새 정점 네 개를 내어 정점이 모두 $5$개가 됩니다. 정점 $1, 2, 3, 4$는 사슬 $1 - 2 - 3 - 4$를 이루고, 정점 $5$도 정점 $3$에 붙습니다.

그다음 야시가 돌아다니기 시작합니다. 첫 이동은 정점 $5$ 방향이므로 야시는 정점 $2$로 갑니다. 정점 $5$ 방향으로의 다음 두 번의 이동으로 야시는 차례로 정점 $3$, 그리고 정점 $5$에 이릅니다. 이어지는 두 번의 이동은 정점 $4$ 방향입니다. 야시는 그곳에 가려고 정점 $3$으로 되돌아와야 합니다. 마지막으로 나무가 정점 $1$에 붙은 여섯 번째 정점을 내고, 야시는 그 방향, 즉 나무 위쪽으로 움직여 정점 $3$에 도착합니다.