13001300 SUSTech Online Judge
Problem 1300 --Pisces and the treasure

1300: Pisces and the treasure

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 81  Solved: 14
[Submit][Status][Web Board]

Description

The evil dragon is defeated, and Pisces can obtain the treasure that the dragon has collected from all over the world! The treasure has many items and each item has a number to indicate how many golds this item is worth. To move them, Pisces has to stack the items up. There are 3 kinds of operations: put one item which is worthy of \(x\) golds at the top of the stack, remove one item at the top of the stack, and query the max value of the items in the stack. Pisces wants you to help him find the answer to each query.

Input

The first line contains 2 integers \(n\) and \(m(1\leq n,m\leq10^5)\) representing the number of items that are initially in the stack and the number of operations.

The second line contains \(n\) integers \(a_1,a_2,a_3,...,a_n(0\leq a_i\leq 10^6)\)representing the values of the items that are initially in the stack, from bottom to top.

Each of the following \(m\) lines contains an operation, where 'P x' means to put an item worthy of \(x(0\leq x\leq 10^6)\) golds to the top of the stack, 'R' to remove the top item, and 'Q' to query the max valued item in the stack. It is guaranteed that all operations are legal.

Output

For each query, print the answer.

Sample Input

5 4
1 2 3 4 5
R
Q
P 10
Q

Sample Output

4
10

HINT

Source

 

[Submit][Status]