현기증 나는 왕위 계승

왕위 계승은 까다로운 주제일 수 있다. 혈통, 성별, 적출 여부, 종교 등 여러 요소를 따져야 하기 때문이다. 보통 왕위는 군주의 자녀가 물려받거나, 자녀가 없는 군주라면 가장 가까운 방계가 물려받는다. 그리 간단하지 않다. 전 세계에서 군주제가 위기에 몰린 이유 중 하나가 바로 이것이다.

그래도 Nlogonia는 아직 군주제로 다스려지고 있으며, 다행히 계승 규칙은 단순하다. 일반적으로 고려할 측면은 두 가지뿐이다. "자녀가 형제보다 먼저" 그리고 "나이가 많은 사람이 어린 사람보다 먼저".

왕실 시종들은 Nlogonia의 초대 통치자 Constant의 혈통을 나무 모양으로 그린 거대한 태피스트리를 관리한다. 새 가족이 태어날 때마다 부모에서 자식으로 이어지는 가지가 태피스트리에 그려진다. 이것은 매우 중요한 사건이어서, 전설에 따르면 Constant의 후손은 자녀의 이름이 태피스트리에 추가되는 것을 보기 전에는 결코 죽지 않는다고 한다. 누군가 죽으면 그 사람의 이름 옆에 십자가가 그려진다. 현 군주가 죽을 때마다 시종들은 태피스트리를 이용해 다음 통치자가 누구인지 결정한다. 그 사람이 누구인지 결정하기 위해 시종들은 Constant에서 시작하여 앞서 설명한 규칙, 즉 "자녀가 형제보다 먼저" 그리고 "나이가 많은 사람이 어린 사람보다 먼저"에 따라 나무를 순회한다. Constant에서 시작해 Constant의 첫 번째 자녀, 그 자녀의 첫 번째 자녀, 이런 식으로 내려가다가 살아 있는 첫 번째 사람에 도달하거나 더 따라갈 자녀가 없는 가족 구성원에 도달하면, 그 사람의 부모로 돌아가 그 부모의 다음 자녀로 이동하고, 새로운 군주가 결정될 때까지 이 과정을 반복한다.

수천 년 동안 권력을 잡아 온 Constant의 혈통은 거대하다. 태피스트리를 관리하고 때가 되면 다음 군주가 누구인지 결정하는 것은 오래 걸리는 작업이어서, Nlogonia의 시종들은 이제 현대화할 때라고 결정했다. 그들은 Constant의 혈통을 관리하고, 통치자가 비참하게 죽은 뒤 다음 군주가 누구인지도 알려 줄 프로그램을 만들고 싶어 한다. 이 일의 중요성을 고려해 왕실 시종들은 지금까지 일어난 모든 사건에 대해 프로그램이 올바른 출력을 내는지 확인하며 시험하려 한다. 문제가 하나 있는데, 그들 중 누구도 프로그래밍을 잘하지 못해서 당신에게 도움을 청하러 온 것이다.

좀 더 기술적으로 말하면, Constant의 혈통에 속한 각 사람은 고유한 양의 정수 식별자로 표현된다. 새 자녀가 태어날 때마다 그 자녀는 다음으로 가장 작은 고유 식별자를 받는다. Constant의 식별자는 1이며, 처음에는 그만이 살아 있다. 처리해야 할 사건이 시간 순서대로 많이 주어진다. 누군가 죽을 때마다 왕실 시종들이 현재 군주가 누구인지 알아내도록 도와야 한다. 통치할 사람이 항상 살아 있음이 보장된다.

첫째 줄에는 처리해야 할 사건의 수를 나타내는 정수 Q(1 ≤ Q ≤ 10^5)가 주어진다. 다음 Q개 줄에는 각각 두 정수 t_i와 x_i가 주어지며, i번째 사건의 유형과 인수를 나타낸다. t_i가 1이면 식별자 x_i인 사람에게 새 자녀가 생겼다는 뜻이다. t_i가 2이면 식별자 x_i인 사람이 죽었다는 뜻이다.

누군가 죽는 각 사건마다 현재 군주의 식별자를 나타내는 정수를 한 줄에 출력한다.