Hiện tại là giờ kiểm tra ở làng của Mirko. Tất cả mọi người đều muốn vượt qua bài kiểm tra với ít nỗ lực nhất có thể. Mirko nhận ra rằng sẽ là tốt nhất nếu anh ấy tìm được ai đó biết nhiều thứ hơn anh ấy và anh ấy có thể học từ họ. Tất cả mọi người đều bắt chước theo và giờ mọi người đều tìm một ai đó để có thể học hỏi từ họ.

Chúng ta có thể đánh giá một học sinh chuẩn bị tốt cho bài kiểm tra như nào với 2 số nguyên, ~A~ và ~B~. Số nguyên ~A~ thể hiện học sinh hiểu đến mức nào về một môn, trong khi số ~B~ tỉ lệ thuận với lượng kiến thức của họ.

Là người đứng đầu của làng, Mirko quyết định một học sinh sẽ xin một học sinh trợ giúp khi và chỉ khi học sinh đó có cả 2 số lớn hơn hoặc bằng với số của học sinh đầu tiên (không học sinh nào xin sự trợ giúp nếu không có ai hiểu môn học bằng họ).

Ngoài ra, các học sinh sẽ cố gắng giảm thiểu sự khác biệt về lượng kiến thức (để học sinh khác không bận tâm đến những kiến thức cao siêu hơn). Nếu lựa chọn này không phải duy nhất, họ sẽ cố gắng giảm thiểu sự khác biệt về độ hiểu biết.

Làng của Mirko gần đây là một vùng ngoài ô nổi tiếng và các học sinh mới chuyển đến nhiều (trong thời gian kiểm tra). Với luật hà khắc của Mirko, họ cảm thấy rất bối rối về luật của Mirko và không biết phải làm gì). Họ quyết định hỏi lập trình viên của ngôi làng bên cạnh cho sự trợ giúp.

Input

Dòng đầu tiên gồm số nguyên ~N~ (~1 <= N <= 200000~), số lượng truy vấn và số lượng người chuyển đến làng. Mỗi ~N~ dòng tiếp theo bao gồm:

• "D A B", một học sinh chuyển đến có độ thông minh A và B.

• "P i", học sinh thứ i chuyển đến cần sự giúp đỡ.

• (~1 <= A, B <= 2 \cdot 10^9~). Không học sinh nào có 2 số bằng nhau.

Output

Với mỗi truy vấn ("P i"), hãy đưa ra học sinh nào mà học sinh thứ i nên xin sự giúp đỡ. Các học sinh được đánh số theo thứ tự họ chuyển vào làng (bắt đầu từ 1). Nếu 1 học sinh không thể được giúp, in ra "NE".

Sample Input 1

6
D 3 1
D 2 2
D 1 3
P 1
P 2
P 3

Sample Output 1

NE
NE
NE

Sample Input 2

6
D 8 8
D 2 4
D 5 6
P 2
D 6 2
P 4

Sample Output 2

3 
1

Sample Input 3

7
D 5 2
D 5 3
P 1
D 7 1
D 8 7
P 3
P 2

Sample Output 3

2
4
4