Handling the Past

Nowadays, cloud computing is a popular topic among business and technology circles. In cloud computing, everything can be stored in a cloud server, and clients deal with the data by sending operation-requests to the server. However, such client-server mode may cause some problems. For example, if you send two operations op1 and op2 to the server, expecting that op1 should be executed first and followed by op2. Due to the network delay, op1 may arrive at the server later than op2. In order to inform the server the correct operation order, each operation is associated with a timestamp. Now if the server gets two operations (op1, t1) and (op2, t2), where t1 < t2, the server will know that op1 should be executed earlier than op2. So, if (op2, t2) arrives first, the server will execute op2 immediately. And when (op1, t1) arrives, the server will find that op1 should be executed before op2 (because t1 < t2), thus it has to undo op2, execute op1, and re-execute op2 finally.

In this problem, you are asked to simulate the above process. To simplify the problem, we assume that there is only a stack, a last-in-first-out data structure as you know, stored in the server. Three types of operations are considered, whose formats and semantics are given as follows.

push x t -- push x into the stack, and t is a timestamp
pop t -- pop the top element from the stack, and t is a timestamp
peak t -- return the top element in the stack, and t is a timestamp

When an operation op with a timestamp t arrives, the server process it in the following three steps:

Step 1: undo all the "push" and "pop" operations having timestamp larger than t.
Step 2: execute op.
Step 3: redo all the "push" and "pop" operations which were undone in step 1.

The server do not need to undo or redo any "peak" operations. In another word, every "peak" operation is executed only once after it arrives at the server.

Given the operations arriving at the server in order, you are asked to simulate the above process. The stack is empty initially. To simplify the problem further, another two assumptions are made:

1. All the "pop" operations are valid. In another word, if you simulate the process correctly, no "pop" operations will be performed on an empty stack.
2. All timestamps are different.

The input contains multiple test cases.

Each case begins with an integer N (1<=N<=50000), indicating the number of operations. The following N lines each contain an operation in one of the following three formats:

push x t
pop t
peak t
where 0<=x, t<=10^9.

The operations are given in the order in which they arrive at the server.
The input is terminated by N = 0.

For each case, output "Case #X:" in a line where X is the case number, staring from 1. Then for each "peak" operation, output the answer in a line. If the stack is empty, output -1 instead.

7
push 100 3
push 200 7
peak 4
push 50 2
pop 5
peak 6
peak 8
4
push 25 1
pop 5
peak 6
peak 3
4
push 10 1
peak 7
pop 3
peak 4
0

Case #1:
100
50
200
Case #2:
-1
25
Case #3:
10
-1

SYSU

2014 Multi-University Training Contest 9