Monarchy in Vertigo

Monarchy succession can be a tricky topic, since it may take multiple factors into account such as descent, sex, legitimacy, and religion. Usually the Crown is inherited by a sovereign's child, or by a childless sovereign's nearest collateral line. Not really straightforward, is it? That is one of the reasons monarchy is on the edge all over the world.

Nlogonia is still ruled by a monarchy, though, luckily with simple succession rules. In general there are only two aspects to take into account: "children come before siblings" and "older comes before younger".

The reign servants maintain a beautiful and enormous tapestry where the bloodline of Constant, Nlogonia's first ruler, is drawn in the shape of a tree. Whenever a new family member is born, a new branch from the parent to the child is drawn in the tapestry. This is such an important event that legend says that when Constant's descendants have a child they will never die before watching their child's name added to the tapestry. When someone dies, a cross is drawn close to that person's name. Whenever the current monarch dies, the tapestry is used by the servants to determine who the next ruler should be. In order to determine who that person is, the servants start from Constant and traverse the tree according to the rules described earlier, "children come before siblings" and "older comes before younger". They descend the tree starting from Constant, followed by Constant's first child, followed by that child's first child, and so on, until reaching the first person alive or a family member that has no children left to follow, in which case they then go back to that person's parent and move into that parent's next child, repeating the process until the new monarch is determined.

After thousands of years in power Constant's bloodline is huge. To maintain the tapestry and, when the time comes, to determine who the next monarch should be are lengthy processes and Nlogonian servants decided it's time to modernize. They want to create a program to be used to maintain Constant's bloodline, which can also point who the next monarch should be after a ruler's tragic death. Given the importance of this task, the monarchy servants want to test the program by checking that it produces the correct output for all events that happened so far. There is one issue though, none of them is really good with programming and that's why they came after you for help.

More technically, each person in Constant's bloodline will be represented by a unique positive integer identifier. Whenever a new child is born, they take the next lowest unique identifier. Constant's identifier is equal to 1, and initially he's the only person alive. You will be given many events to process, in chronological order. Whenever someone dies, you should help the monarchy servants to figure out who the current monarch is. It's guaranteed that there will always be someone alive to rule.

The first line contains an integer Q (1 ≤ Q ≤ 10^5), representing how many events should be processed. The following Q lines contain two integers t_i and x_i each, representing the i-th event type and argument. If t_i is equal to 1, then it means that person with identifier x_i had a new child. If t_i is equal to 2, then it means that person with identifier x_i died.

For each event in which someone dies, you should print a line with an integer, representing the identifier of the current monarch.