Problem A
Trees

Tom is observing a line of many trees along the horizon, from the window of his room. All trees are planted at positive integer positions along one straight line (imagine a number line). There can only be at most one tree (or no tree) at each position. Each tree has a positive integer volume. Tom has developed a way to determine the volume of trees accurately, and excited he is.

Jerry loves to uproot trees and swap them with new trees, so every time Tom looks out of the window, he realizes the trees in the line keep changing shape/size and hence volume. Excited Jerry is.

As Tom observes the trees and as Jerry changes the landscape, help Tom figure out the largest tree within a range of positions. There are 2 possible operations:

1. $\mathbf{u}$ $\mathbf{P}$ $\mathbf{V}$ : Jerry first uproots the tree at position $\mathbf{P}$ if there is one, then/otherwise plants a new tree with volume $\mathbf{V}$ there. Return the volume of the uprooted tree if there was one, or 0 if no tree was uprooted.

2. $\mathbf{?}$ $\mathbf{L}$ $\mathbf{R}$ : Tom is interested in the space between positions $\mathbf{L}$ and $\mathbf{R}$ inclusive. Return the volume of the largest tree within that space, or 0 if there are no trees within that space.

Assume that initially, there are no trees.

Input

The first line contains $\mathbf{Q}$ ($1 \le \mathbf{Q} \le 200,000$) the number of operations to perform.

Each of the next $\mathbf{Q}$ lines contains one of the 2 operations described above. Each $\mathbf{P}$, $\mathbf{V}$, $\mathbf{L}$, $\mathbf{R}$ is a positive integer ($\mathbf{L} \le \mathbf{R}$ and $1 \le \mathbf{P},\mathbf{V},\mathbf{L},\mathbf{R} < 10^{9}$).

Output

One line for the result of each of the $\mathbf{Q}$ operations (which will either be the volume of a tree, or 0 if no tree exists).

13
? 1 7
u 3 5
? 1 7
u 7 6
? 1 7
u 3 8
? 1 7
u 7 4
? 1 7
u 3 2
? 1 7
? 1 4
? 5 6

0
0
5
0
6
5
8
6
8
8
4
2
0

13
u 3 5
u 7 3
u 10 2
u 15 7
u 19 4
? 3 19
? 3 14
u 15 1
? 9 20
? 17 17
u 10 20
? 3 14
? 14 20

0
0
0
0
0
7
5
7
4
0
2
20
4