Cow Line

Farmer John's cows are forming a single line. The line starts empty, and as time passes the cows join it one at a time, at either the left end or the right end. Every so often, $K$ cows at the left end or the right end all leave the line at once to go graze.

The cows join in numerical order ($1, 2, 3, \dots$): each time a cow arrives, it is assigned the smallest number not yet used. Once a cow leaves the line, it never returns.

You are given $S$ operations ($1 \le S \le 100{,}000$). Each operation is one of the following two kinds:

• A cow joins the left end or the right end of the line.
• $K$ cows leave from the left end or the right end of the line.

The input never asks for an operation that cannot be performed (for example, removing more cows than are currently in the line).

After processing all operations, print the numbers of the cows remaining in the line from left to right. The final line is guaranteed to be non-empty.

• Line 1: an integer $S$.
• Lines 2 to $S+1$: each line contains one operation in one of four formats:
  • A L — a cow joins the left end of the line.
  • A R — a cow joins the right end of the line.
  • D L K — $K$ cows leave from the left end.
  • D R K — $K$ cows leave from the right end.

Print the numbers of the cows remaining in the line from left to right, one number per line.

The table below traces how each operation changes the line for a sample sequence of ten operations.