Deda (Deda)

Nguồn: COCI

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ đứa trẻ, tuổi của chúng lần lượt là $1,2,\ldots,N$. Một chuyến tàu xuất phát ở ga $0$ rồi đi qua các ga $1,2,3,\ldots$.

Các câu kể xuất hiện theo thứ tự bất kỳ. Có $Q$ dòng, mỗi dòng thuộc một trong hai loại:

• M X A: cho biết đứa trẻ tuổi $A$ xuống tàu ở ga $X$.
• D Y B: trong những đứa trẻ có tuổi ít nhất $B$, hãy tìm đứa trẻ nhỏ tuổi nhất mà theo các câu kể đã biết đến thời điểm hiện tại, nó xuống tàu không muộn hơn ga $Y$.

Nếu chưa từng có câu M cho một đứa trẻ thì xem như nó xuống ở vô cùng. Mỗi đứa trẻ xuất hiện trong nhiều nhất một câu M.

Input

Dòng đầu chứa $N,Q$.

$Q$ dòng tiếp theo có dạng M X A hoặc D Y B.

Giới hạn chung: $1\le X,Y\le10^9$, $1\le A,B\le N$. Có ít nhất một truy vấn D.

Output

Với mỗi truy vấn D, in tuổi của đứa trẻ cần tìm. Nếu không tồn tại, in -1.

Subtask

• Subtask 1 — 20%: $2\le N,Q\le50$.
• Subtask 2 — 30%: $2\le N,Q\le5000$.
• Subtask 3 — 50%: $2\le N,Q\le2\cdot10^5$.

Ví dụ

Input

3 4
M 10 3
M 5 1
D 20 2
D 5 1

Output

3
1

Giải thích

Sau hai câu M, trong nhóm tuổi từ $2$ trở lên chỉ tuổi $3$ đã biết xuống trước ga $20$, nên truy vấn đầu trả $3$. Truy vấn sau cho phép tuổi từ $1$ và ga tối đa $5$, nên trả $1$.