Range Minimum Query

The Giggle company opens their office in Sudislavl and you are invited to interview. Your task is to solve the given problem.

You need to create a data structure that stores an array of integers. Initially, the array is empty. You need to support two operations:

• query: "? i j" - returns the minimum element between the i-th and j-th inclusively;

• update: "+ i x" - add element x after the i-th element in array. If i = 0, the element is added to the beginning of array.

Of course, this structure should be good enough.

Input

The first line contains the number of operations n (1 ≤ n ≤ 200000) on array. Next n lines describe the operations. All update operations are correct. All numbers stored in the array do not exceed 10^9.

Output

For each operation ? print on a separate line its result.

Examples