Crossroad

The capital of Flatland, the city of New Fletsity, was built by a wise mayor who wanted fewer road accidents. Every intersection in the city is formed by two roads crossing at a right angle. Seen from the observation deck of the Fletstate Building, the city looks like a huge number of identical squares, each bounded by roads, with four intersections at its corners. All intersections have four sides, so the traffic rules are simple and clear.

One day, Seryozha, a young resident of New Fletsity, decided to get a driving license and enrolled in a driving school. The first lesson covered the rules for crossing intersections of unequal roads. The rules have three points.

• At an intersection of unequal roads, a driver on the minor road must yield to vehicles approaching on the main road.
• If the main road changes direction at the intersection, drivers on the main road must follow the rules for crossing intersections of equal roads among themselves.
• At an intersection of equal roads, a driver must yield to vehicles approaching from the right.

The teacher then gave Seryozha a whole set of problems. Since Seryozha lives in New Fletsity, where all intersections have four sides, every problem asks in what order N cars will pass the intersection. The cars approach from each of the four sides at set moments. The sides are numbered 1, 2, 3 and 4 clockwise. At most one car arrives from each side per unit of time. All drivers are polite enough not to break the crossing rules or overtake the cars ahead. Every car wants to go straight. Cars approaching from sides a and b are on the main road. The rest are on the minor road.

A car passes the intersection only if:

• no car stands ahead of it in the queue to the intersection, and
• no car it must yield to is left.

If the first two cars in line do not have to yield to each other, they cross at the same time.

Help Seryozha solve all the problems.

The first line contains one integer N (1 \le N \le 100), the number of vehicles. The second line contains the numbers a and b (1 \le a,b \le 4, a \ne b), the sides that form the main road.

Each of the next N lines contains two integers d_i and t_i (1 \le d_i \le 4, 1 \le t_i \le 100), the direction and the arrival time of the i-th vehicle.

Print N integers, one per line. The i-th line must contain the time at which the i-th vehicle passes the intersection.

Vehicles are numbered in the order they appear in the input.