Problem E. Empire ≡

Statement

The Galactic Empire consists of numerous star systems. Each system has its own number. The capital world, Trantor, has number 1. Initially, thousands years ago, the empire consisted of Trantor only. All other star systems were captured by the Empire and each next system was receiving the next natural number (2, 3, etc.).

In order to keep the Empire connected, each newly captured system was connected by a hyper-tunnel with exactly one of the systems belonging to the Empire at the moment of capture. Captures is the only case when the Empire builds hyper-tunnels.

Some of the systems were disconnecting from the Empire and were never captured again. In order to disconnect from the empire, rebels destroy the hyper-tunnel that was built to connect them with the Empire. Some other systems also may become disconnected from the Empire at that moment and the Empire loses them too.

Hari Seldon is looking for a perfect star system for Foundation. He reconstructed the whole history of the Empire and represented it as a sequence of events: captures and disconnections. After each event he needs to know the number of the system which is the most remote from Trantor (i.e., the distance between Trantor and the system should be maximal, that's what we considers as the best place for Foundation). The distance from one system to another is measured as minimal number of hyper-tunnels that one need to pass in order to get from one system to another. If there are several most remote systems, Hari can take any of them.

Unfortunately, software engineers are quite rare in the Empire. Luckily, Hari found you and asked you to help him. You should write a program that, given the history of the Empire, will tell which world is the most remote after each event.

In the example given below, there are 5 events:

1. Add new system and connect it to system 1. New system receives number 2 and becomes the most remote system.
2. Add new system and connect it to system 2. New system receives number 3 and becomes the most remote system.
3. Add new system and connect it to system 1. New system receives number 4, but the most remote system is still 3.
4. Disconnect system 2. System 3 also appears disconnected and thus the most remote system is 4.
5. Add new system and connect it to system 4. New system receives number 5 and becomes the most remote system.

Input file format

The first line of the input file contains integer number N — number of historical events. The description of events in chronological order follows starting from the second line of the input. Each event is written in a single line. If the event is adding a new system to the Empire, then it's written as " + V" where V is the number of the system in the Empire that new system got connected with (the new system receives next integer number in the sequence of system numbers). Disconnections are written as " − V" which means that the system V is disconnected from the Empire.

All input data is correct, i.e. only a system that is connected to the Empire can be disconnected, new systems will be connected only to the ones that belong to the Empire, Trantor is never disconnected.

Output file format

For each event from the input file, print the number of the system which is the most remote from Trantor. In case several solutions exist, output any of them.

Constraints

1 ≤ N ≤ 200000;

Sample tests

5
+1
+2
+1
-2
+4

2
3
3
4
5