Question 1:

Farmer John's storage is a very tall

but narrow room that only one haybale can fit with respect to the width and

the length. So the haybales can only be stored by stacking them starting

from the floor. Initially the storage is empty and there are

haybales numbered starting from 1 in the warehouse.

FJ has a robot equipped with one arm that can hold one haybale.

He controls the robot with two commands: ADD and REMOVE.

With ADD command, the robot takes the next haybale in the warehouse and

puts it on top of the haybales in the storage. When it receives REMOVE

command it takes the haybale on the top in the storage and carries it

to the barn. At the end of the week, FJ wants to learn the status of

the storage in terms of the list of the haybales.

Your program will help FJ to find out the list of the haybales.

For example, given the sequence of FJ's commands throughout the week,

the list of the haybales in the storage will be as follow:

Command​ ​ Storage

=======​ ​ =======

ADD​ ​ 1

ADD​ ​ 12

ADD​ ​ 123

ADD​ ​ 1234

REMOVE​ ​ 123

ADD​ ​ 1235

ADD​ ​ 12356

REMOVE​ ​ 1235

REMOVE​ ​ 123

REMOVE​ ​ 12
ADD​ ​ 127

ADD​ ​ 1278

REMOVE​ ​ 127

REMOVE​ ​ 12

REMOVE​ ​ 1

REMOVE​ ​

ADD​ ​ 9

ADD​ ​ 9 10

REMOVE​ ​ 9

ADD​ ​ 9 11

Finally, the haybales numbered 9 and 11 will remain in the storage.

PROBLEM NAME: robo

INPUT FORMAT:

* Line 1: A single integer: N <= 1,000,000, the number FJ's commands

* Lines 2..N+1: The sequence of FJ's commands

SAMPLE INPUT:

20

ADD

ADD

ADD

ADD

REMOVE

ADD

ADD

REMOVE
REMOVE

REMOVE

ADD

ADD

REMOVE

REMOVE

REMOVE

REMOVE

ADD

ADD

REMOVE

ADD

OUTPUT FORMAT:

* Line 1: M, the number of haybales remained in the storage

* Lines 2..M+1: The list of haybales starting from bottom to top.

SAMPLE OUTPUT:

11

Question 2:

Bessie likes shopping at CowMart. She is also curious about the

payment system at the registers. There are less than 1,000

the end of the line. When a register is available,the next customer

in front of the line goes to the register and pays. Bessie would

like to know which customers payed at which register at the end of

the day. Initially there are no customers in the store. A customer

can pay then buy something again. In that case, the customer

has to enter the line at the end again. The number of registers

in the store is 0 < N <= 30.

As an example, there are 5 customers and 3 registers

in the store. The sequence of available registers and customers to

enter the line is given as follows:

Process Line Register 1 Register 2 Register 3

==== ==== === === ===

C1 1

C5 15

C3 153

R3 53 1

C2 532 1

R3 32 15

C5 325 15

R2 25 3 15

C4 254 3 15

C1 2541 3 15

R3 541 3 152

C3 5413 3 152

R2 413 35 152

R1 13 4 35 152

C5 135 4 35 152

C2 1352 4 35 152

R2 352 4 351 152

R1 2 45 3513 152

R1 452 3513 152

Here 'C' corresponds to the customer and 'R' corresponds to the register.

Then the list of the customers payed at the registers are as follows:

Register 1: 4 5 2

Register 2: 3 5 1 3

Register 3: 1 5 2

PROBLEM NAME: shoppay

INPUT FORMAT:

* Line 1: N, the number of registers in the store.

* Line 2..end-of-file: Each line is ither C then followed by customer number

or R then followed by register number. Number of lines is less than 10,000.

SAMPLE INPUT:

C1

C5

C3

R3

C2

R3

C5

R2

C4
C1

R3

C3

R2

R1

C5

C2

R2

R2

R1

R1

OUTPUT FORMAT:

* Line 1..N: Line i has R_i, the number of customers in that register,

then R_i numbers corresponding to the list of the customers payed at register i

ordered from the earliest to latest.

SAMPLE OUTPUT:

3452

43513

3152

Question 3:

Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered

1..N, are once again standing in a row. Cow i has height H_i (1 <=
H_i <= 1,000,000).

Each cow is looking to her left toward those with higher index

numbers. We say that cow i 'looks up' to cow j if i < j and H_i <

H_j. For each cow i, FJ would like to know the index of the first

cow in line looked up to by cow i.

Note: about 50% of the test data will have N <= 1,000.

PROBLEM NAME: lookup

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains the single integer: H_i

SAMPLE INPUT:

INPUT DETAILS:

FJ has six cows of heights 3, 2, 6, 1, 1, and 2.

OUTPUT FORMAT:
* Lines 1..N: Line i contains a single integer representing the

smallest index of a cow up to which cow i looks. If no such

cow exists, print 0.

SAMPLE OUTPUT:

OUTPUT DETAILS:

Cows 1 and 2 both look up to cow 3; cows 4 and 5 both look up to cow 6; and

cows 3 and 6 do not look up to any cow.

Question 4:

Farmer John has devised a brilliant method to paint the long fence next to

his barn (think of the fence as a one-dimensional number line). He simply

attaches a paint brush to his favorite cow Bessie, and then retires to

drink a cold glass of water as Bessie walks back and forth across the

fence, applying paint to any segment of the fence that she walks past.

Bessie starts at position 0 on the fence and follows a sequence of N

moves (1 <= N <= 100,000). Example moves might be "10 L", meaning
Bessie moves 10 units to the left, or "15 R", meaning Bessie moves 15

units to the right. Given a list of all of Bessie's moves, FJ would

like to know what area of the fence gets painted with at least K coats

of paint. Bessie will move at most 1,000,000,000 units away from the

origin during her walk.

PROBLEM NAME: paint

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K.

* Lines 2..1+N: Each line describes one of Bessie's N moves (e.g., "15

L").

SAMPLE INPUT (file paint.in):

62

2R

6L

1R

8L

1R

2R

INPUT DETAILS:

Bessie starts at position 0 and moves 2 units to the right, then 6 to the

left, 1 to the right, 8 to the left, and finally 3 to the right. FJ wants

to know the area covered by at least 2 coats of paint.

* Line 1: The total area covered by at least K coats of paint.

SAMPLE OUTPUT (file paint.out):

OUTPUT DETAILS:

6 units of area are covered by at least 2 coats of paint. This includes

the intervals [-11,-8], [-4,-3], and [0,2].