시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 257 97 29 29.592%

문제

홍준이는 동아리에서 스터디장을 맡고 있다. 이 스터디에 오는 사람들의 주된 목표는 다 같이 모여서 공부를 하는 것이 아닌 모르는 것을 질문하는 것 이다. 홍준이도 이러한 점을 잘 알고 있다.

스터디에 있는 학생들의 능력을 두 개의 자연수 A와 B로 표현할 수 있다. A는 학생이 얼마나 잘 이해하고 있는지를 나타내고, B는 이 과목에 대한 학생의 지식의 깊이 정도를 나타낸다. 물론 값이 클 수록 이해를 더 잘하고, 지식의 깊이가 깊은 것을 의미한다.

스터디에 있는 학생은 자신 보다 이해를 못하거나, 지식의 깊이가 낮은 학생한테 질문하지 않는다. 하지만, 지식의 깊이가 같고, 자신보다 이해를 잘한 학생한테는 질문한다. 동시에 지식의 깊이 차이가 최소인 학생에게 질문하고 싶어한다. 만약 지식의 깊이 차이가 최소인 사람이 여러 명인 경우, 이해 정도의 차이가 최소인 사람한테 질문하고 싶어한다.

홍준이는 학생들의 이러한 성향을 매우 잘 파악하고 있고, 종종 학생들로부터 누구한테 질문하면 좋겠냐는 질문을 받는다. 홍준이를 도와 학생들의 질문에 대답해주는 프로그램을 작성하시오.

시간이 지남에 따라 동아리에 사람이 더 가입한다. 동아리를 탈퇴하는 사람은 없다.

입력

첫 줄에는 상황의 수 N이 주어진다. (1 ≤ N ≤ 200 000)

그 다음 N개의 줄에 다음과 같은 2가지 종류의 상황이 주어진다.

  • "D A B", 이해의 정도가 A이고, 지식의 깊이가 B인 학생이 동아리에 가입한다.
  • "P i", i번째로 가입한 학생이 누구한테 질문을 해야하는지 물어온다.

주어지는 수 A, B는 1이상, 2ㆍ10 9 이하다. 그리고 A, B가 동일한 학생은 존재하지 않는다.

출력

각 줄에 "P i"의 상황에 대한 답을 출력해야 한다. 만약 질문할 수 있는 학생이 존재하지 않는 경우 "NE"를 출력한다. 만약 i번째로 가입한 학생이 질문하는 학생이 k번째로 동아리에 가입했다면, 수 k를 출력한다.

예제 입력 1

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

예제 출력 1

NE
NE
NE
W3sicHJvYmxlbV9pZCI6IjMwMzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWQxMzBcdWI1MTRcdWM3YTUgXHVkNjRkXHVjOTAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgXHViM2Q5XHVjNTQ0XHViOWFjXHVjNWQwXHVjMTFjIFx1YzJhNFx1ZDEzMFx1YjUxNFx1YzdhNVx1Yzc0NCBcdWI5ZTFcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjMmE0XHVkMTMwXHViNTE0XHVjNWQwIFx1YzYyNFx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHVjOGZjXHViNDFjIFx1YmFhOVx1ZDQ1Y1x1YjI5NCBcdWIyZTQgXHVhYzE5XHVjNzc0IFx1YmFhOFx1YzVlY1x1YzExYyBcdWFjZjVcdWJkODBcdWI5N2MgXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHViYWE4XHViOTc0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM5YzhcdWJiMzhcdWQ1NThcdWIyOTQgXHVhYzgzIFx1Yzc3NFx1YjJlNC4gXHVkNjRkXHVjOTAwXHVjNzc0XHViM2M0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWM4MTBcdWM3NDQgXHVjNzk4IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJhNFx1ZDEzMFx1YjUxNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YjJhNVx1YjgyNVx1Yzc0NCBcdWI0NTAgXHVhYzFjXHVjNzU4Jm5ic3A7XHVjNzkwXHVjNWYwXHVjMjE4IEFcdWM2NDAgQlx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gQVx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNWJjXHViOWM4XHViMDk4IFx1Yzc5OCBcdWM3NzRcdWQ1NzRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgQlx1YjI5NCBcdWM3NzQgXHVhY2ZjXHViYWE5XHVjNWQwIFx1YjMwMFx1ZDU1YyZuYnNwO1x1ZDU1OVx1YzBkZFx1Yzc1OCZuYnNwO1x1YzljMFx1YzJkZFx1Yzc1OCBcdWFlNGFcdWM3NzQmbmJzcDtcdWM4MTVcdWIzYzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWJiM2NcdWI4NjAgXHVhYzEyXHVjNzc0IFx1ZDA3NCBcdWMyMThcdWI4NWQgXHVjNzc0XHVkNTc0XHViOTdjIFx1YjM1NCBcdWM3OThcdWQ1NThcdWFjZTAsIFx1YzljMFx1YzJkZFx1Yzc1OCZuYnNwO1x1YWU0YVx1Yzc3NFx1YWMwMCBcdWFlNGFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHVkMTMwXHViNTE0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVjNzkwXHVjMmUwIFx1YmNmNFx1YjJlNCBcdWM3NzRcdWQ1NzRcdWI5N2MgXHViYWJiXHVkNTU4XHVhYzcwXHViMDk4LCBcdWM5YzBcdWMyZGRcdWM3NTggXHVhZTRhXHVjNzc0XHVhYzAwIFx1YjBhZVx1Yzc0MCBcdWQ1NTlcdWMwZGRcdWQ1NWNcdWQxNGMgXHVjOWM4XHViYjM4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM5YzBcdWMyZGRcdWM3NTggXHVhZTRhXHVjNzc0XHVhYzAwIFx1YWMxOVx1YWNlMCwgXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1Yzc3NFx1ZDU3NFx1Yjk3YyBcdWM3OThcdWQ1NWMgXHVkNTU5XHVjMGRkXHVkNTVjXHVkMTRjXHViMjk0IFx1YzljOFx1YmIzOFx1ZDU1Y1x1YjJlNC4gXHViM2Q5XHVjMmRjXHVjNWQwIFx1YzljMFx1YzJkZFx1Yzc1OCBcdWFlNGFcdWM3NzQgXHVjYzI4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1Yzc3OCBcdWQ1NTlcdWMwZGRcdWM1ZDBcdWFjOGMgXHVjOWM4XHViYjM4XHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzljMFx1YzJkZFx1Yzc1OCBcdWFlNGFcdWM3NzQgXHVjYzI4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1Yzc3OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNWVjXHViN2VjIFx1YmE4NVx1Yzc3OCBcdWFjYmRcdWM2YjAsIFx1Yzc3NFx1ZDU3NCBcdWM4MTVcdWIzYzRcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1Yzc3OCBcdWMwYWNcdWI3OGNcdWQ1NWNcdWQxNGMgXHVjOWM4XHViYjM4XHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjRkXHVjOTAwXHVjNzc0XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMTMxXHVkNWE1XHVjNzQ0IFx1YjllNFx1YzZiMCBcdWM3OTggXHVkMzBjXHVjNTQ1XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjODg1XHVjODg1IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWIyMDRcdWFkNmNcdWQ1NWNcdWQxNGMgXHVjOWM4XHViYjM4XHVkNTU4XHViYTc0IFx1Yzg4Ylx1YWNhMFx1YjBkMFx1YjI5NCBcdWM5YzhcdWJiMzhcdWM3NDQgXHViYzFiXHViMjk0XHViMmU0LiBcdWQ2NGRcdWM5MDBcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM1ZDAgXHViMzAwXHViMmY1XHVkNTc0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM5YzBcdWIwYThcdWM1ZDAgXHViNTMwXHViNzdjIFx1YjNkOVx1YzU0NFx1YjlhY1x1YzVkMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViMzU0IFx1YWMwMFx1Yzc4NVx1ZDU1Y1x1YjJlNC4gXHViM2Q5XHVjNTQ0XHViOWFjXHViOTdjIFx1ZDBjOFx1ZDFmNFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWQ2NjlcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyMDAgMDAwKTxcL3A+XHJcblxyXG48cD5cdWFkZjgmbmJzcDtcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCAyXHVhYzAwXHVjOWMwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMwYzFcdWQ2NjlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiZxdW90O0QgQSBCJnF1b3Q7LCBcdWM3NzRcdWQ1NzRcdWM3NTggXHVjODE1XHViM2M0XHVhYzAwIEFcdWM3NzRcdWFjZTAsIFx1YzljMFx1YzJkZFx1Yzc1OCBcdWFlNGFcdWM3NzRcdWFjMDAgQlx1Yzc3OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViM2Q5XHVjNTQ0XHViOWFjXHVjNWQwIFx1YWMwMFx1Yzc4NVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+JnF1b3Q7UCBpJnF1b3Q7LCBpXHViYzg4XHVjOWY4XHViODVjIFx1YWMwMFx1Yzc4NVx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViMjA0XHVhZDZjXHVkNTVjXHVkMTRjIFx1YzljOFx1YmIzOFx1Yzc0NCBcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTRcdWM5YzAgXHViYjNjXHVjNWI0XHVjNjI4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMTggQSwgQlx1YjI5NCAxXHVjNzc0XHVjMGMxLCZuYnNwOzJcdTMxOGQxMCA8c3VwPjk8XC9zdXA+Jm5ic3A7XHVjNzc0XHVkNTU4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgQSwgQlx1YWMwMCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVkNTU5XHVjMGRkXHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YzkwNFx1YzVkMCZuYnNwOyZxdW90O1AgaSZxdW90O1x1Yzc1OCBcdWMwYzFcdWQ2NjlcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjOWM4XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTU5XHVjMGRkXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHVjNmIwICZxdW90O05FJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIGlcdWJjODhcdWM5ZjhcdWI4NWMgXHVhYzAwXHVjNzg1XHVkNTVjIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM5YzhcdWJiMzhcdWQ1NThcdWIyOTQgXHVkNTU5XHVjMGRkXHVjNzc0IGtcdWJjODhcdWM5ZjhcdWI4NWMgXHViM2Q5XHVjNTQ0XHViOWFjXHVjNWQwIFx1YWMwMFx1Yzc4NVx1ZDU4OFx1YjJlNFx1YmE3NCwgXHVjMjE4IGtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJU1BJVEkiLCJkZXNjcmlwdGlvbiI6IjxwPkl0JiMzOTtzIGV4YW0gdGltZSBpbiBNaXJrbyYjMzk7cyB2aWxsYWdlLiBFdmVyeW9uZSB3YW50cyB0byBwYXNzIHRoZSBleGFtIHdpdGggYXMgbGl0dGxlIGVmZm9ydCBhcyBwb3NzaWJsZSwgd2hpY2ggaXMgbm90IGVhc3kuIE1pcmtvIHJlYWxpemVkIHRoYXQgaXQgd291bGQgYmUgYmVzdCBmb3IgaGltIHRvIGZpbmQgc29tZW9uZSB3aG8ga25vd3MgbW9yZSB0aGFuIGhpbSBhbmQgbGVhcm4gZnJvbSB0aGVtLiBFdmVyeW9uZSBmb2xsb3dlZCBhbmQgbm93IGV2ZXJ5b25lIGlzIGxvb2tpbmcgZm9yIHNvbWVvbmUgdG8gbGVhcm4gZnJvbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2UgY2FuIG1vZGVsIGhvdyB3ZWxsIGEgc3R1ZGVudCBpcyBwcmVwYXJlZCBmb3IgdGhlIGV4YW0gd2l0aCB0d28gaW50ZWdlcnMsIEEgYW5kIEIuIFRoZSBudW1iZXIgQSByZXByZXNlbnRzIGhvdyB3ZWxsIGEgc3R1ZGVudCB1bmRlcnN0YW5kcyB0aGUgc3ViamVjdCwgd2hpbGUgdGhlIG51bWJlciBCIGlzIHByb3BvcnRpb25hbCB0byB0aGUgcXVhbnRpdHkgb2YgdGhlaXIga25vd2xlZGdlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BcyB0aGUgaGVhZCBvZiB0aGUgdmlsbGFnZSwgTWlya28gZGVjaWRlZCB0aGF0IGEgc3R1ZGVudCB3aWxsIGFzayBhbm90aGVyIHN0dWRlbnQgZm9yIGhlbHAgb25seSBpZiB0aGF0IHN0dWRlbnQgaGFzIGJvdGggbnVtYmVycyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIGZpcnN0IHN0dWRlbnQmIzM5O3MgbnVtYmVycyAobm8gc3R1ZGVudCB3aWxsIGFzayBzb21lb25lIHdobyBkb2VzbiYjMzk7dCB1bmRlcnN0YW5kIHRoZSBzdWJqZWN0IGFzIHdlbGwgYXMgdGhlbXNlbHZlcyBvciB3aG8ga25vd3MgbGVzcykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFkZGl0aW9uYWxseSwgc3R1ZGVudHMgd2lsbCB0cnkgdG8gbWluaW1pemUgdGhlIGRpZmZlcmVuY2UgaW4ga25vd2xlZGdlIHF1YW50aXR5IChzbyB0aGF0IHN0dWRlbnRzIGRvbiYjMzk7dCBib3RoZXIgdGhvc2UgdGhhdCBhcmUgd2F5IGJldHRlcikuIElmIHRoaXMgY2hvaWNlIGlzIG5vdCB1bmlxdWUsIHRoZXkgd2lsbCB0cnkgdG8gbWluaW1pemUgdGhlIGRpZmZlcmVuY2UgaW4gdW5kZXJzdGFuZGluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28mIzM5O3MgdmlsbGFnZSBoYXMgcmVjZW50bHkgYmVjb21lIGEgdmVyeSBwb3B1bGFyIHN1YnVyYiBhbmQgbmV3IHN0dWRlbnRzIGtlZXAgbW92aW5nIGluIChpbiB0aW1lIGZvciB0aGUgZXhhbSkuIFdpdGggTWlya28mIzM5O3Mgc3RyaWN0IHJ1bGVzLCB0aGV5IGdldCBjb25mdXNlZCBhYm91dCBNaXJrbyYjMzk7cyBydWxlcyBhbmQgZG9uJiMzOTt0IGtub3cgd2hlcmUgdG8gZ28pLiBUaGV5IGRlY2lkZWQgdG8gYXNrIGEgcHJvZ3JhbW1lciBmcm9tIGEgbmVpZ2hib3VyaW5nIHZpbGxhZ2UgZm9yIGhlbHAuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMjAwIDAwMCksIHRoZSBudW1iZXIgb2YgcXVlcmllcyBhbmQgYXJyaXZhbHMgaW4gdGhlIHZpbGxhZ2UuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGVpdGhlcjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mcXVvdDtEIEEgQiZxdW90OywgYSBzdHVkZW50IGhhcyBtb3ZlZCBpbiB3aG9zZSBrbm93bGVkZ2UgaXMgQSBhbmQgQjxcL2xpPlxyXG5cdDxsaT4mcXVvdDtQIGkmcXVvdDssIHRoZSBpLXRoIHN0dWRlbnQgdG8gbW92ZSBpbiB3YW50cyB0byBrbm93IHdob20gdG8gYXNrIGZvciBoZWxwJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIG51bWJlcnMgQSBhbmQgQiBhcmUgYmV0d2VlbiAxIGFuZCAyJm1pZGRvdDsxMDxzdXA+OTxcL3N1cD4uIE5vIHR3byBzdHVkZW50cyBoYXZlIGJvdGggbnVtYmVycyBlcXVhbC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVyeSAoJnF1b3Q7UCBpJnF1b3Q7IGxpbmUpLCBvdXRwdXQgd2hpY2ggc3R1ZGVudCB0aGUgaS10aCBzdHVkZW50IHNob3VsZCBhc2sgZm9yIGhlbHAuIFRoZSBzdHVkZW50cyBhcmUgbnVtYmVyZWQgaW4gdGhlIG9yZGVyIHRoZXkgbW92ZWQgaW50byB0aGUgdmlsbGFnZSAoc3RhcnRpbmcgZnJvbSAxKS4gSWYgYSBzdHVkZW50IGNhbm5vdCBiZSBoZWxwZWQsIG91dHB1dCAmcXVvdDtORSZxdW90Oy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=