Stack Data Structure

Cleaning the Dishes

Bessie and Canmuu are teaming up to wash the massive pile of n (1n10000) dirty dishes left over after the CowMoose Festival. Bessie is washing the dishes; Canmuu will dry them.

Each dish has a unique serial number in the range 1..n. At the beginning, the dishes are stacked in order with 1 on the top and n on the bottom.

Bessie first washes some number of dishes Di by taking one from the top of the incoming pile, washing it, and then stacking it on the other side of the sink (this reverses the order of those dishes).

Once she has finished washing those dishes, either she washes another set of dishes or Canmuu comes back to dry Di dishes while Bessie goes off to eat her well-earned snack. He takes those dishes, one by one, off the stack that Bessie left him, dries the dish, and stacks it (again in reverse order) in the 'cleaned' stack.

Canmuu then either takes another set of dishes to dry or goes off to get a snack while Bessie comes back to wash. They repeat these operations until all of the dishes are washed and dried.

What is the final order (top to bottom) in which the clean, dry dishes are stacked?

To illustrate, suppose that Bessie has a stack of 5 dishes to wash:


D1 is 3, so Bessie takes three dishes from the top of the stack, one by one, washes them, and stacks on the other side of the sink for Canmuu to dry:


Canmuu dries two of these, one by one, and place them onto the clean stack:


Bessie washes the final two dishes:


Finally, Canmuu dries the last three dishes, stacking them in the resulting order below:


So the final order is: 1, 4, 5, 2, 3.

Each of the main input lines contains both a command, Ci (1Ci2) where 1 indicates Bessie washing while 2 indicates Canmuu drying, and the number of dishes Di (1Din) to be washed or dried.


First line contains n - the number of dishes to wash and dry.

Starting from the second, each line contains a command and a count of dishes to process: Ci and Di.


Print n lines: i-th line contains the i-th cleaned dish, starting from the top.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1 3
2 2
1 2
2 3
Output example #1
Source 2011 USACO January, Bronze