Recently I have seen this question in coding Kaze organised by coding Ninja . Can anyone help with the approach .

Amaira is telling a fairy tale to her grandmother . In her tale ,

There are N students denoted with numbers from 1 to N by their age (from the youngest denoted with 1, to oldest with N) , embarked on a train ride. The train leaves from the station 0 and stops in order at stations 1,2,3,.....upto infinity .

Each of the following Amaira statements is of the form " M X A means at stop X child A got out" , where the order of these statements is completely arbitrary. In other words, it doesnot depend on the station order . Her grandmother sometimes asks a question of the form: "D Y B means based on the statements so far, of the children denoted with the number greater than or equal to B, who is the youngest child that rode for Y or less stops ?" If at the moment the grandmother asks the question it hasn't been said so far that a child is getting off the train we assume that the child is riding for an infinite amount of stops.

For each grandmother's question output index of the required child in its own line. If no such child exists output "-1" .

Constraints

2 <= N,Q <=200000

1 <= X,Y <= 1e9 ; 1 <= A,B <=N

Input:

3 4

M 10 3

M 5 1

D 20 2

D 5 1

Output:

3

1