우상단 최근접 점

이차원 좌표평면이 있고, 총 Q개의 아래 두 종류 중 하나의 쿼리가 주어진다.

D\ X\ Y: (X,Y) 좌표에 점을 하나 찍는다.
P\ i: i번째 점보다 우상단에 위치한 점들 중 가장 가까운 점이 몇 번째 점인지 출력한다.
- 점 A의 우상단의 점 B는 X_A \le X_B라는 조건과 Y_A \le Y_B라는 조건을 동시에 만족한다.
- 가장 가까운 점은 Y 좌표의 차이가 가장 작은 점을 의미한다. 단, 그러한 조건을 만족하는 점이 여럿인 경우 X 좌표의 차이가 가장 작은 점을 의미한다.

Q개의 쿼리에 적절히 대응하는 프로그램을 작성하시오.

입력

첫 번째 줄에 쿼리의 수 Q이 주어진다. (1 ≤ Q ≤ 200\ 000)

다음 Q개의 줄에 문제에서의 설명과 동일한 2가지 종류의 쿼리가 주어진다.

주어지는 수 X,Y는 1이상, 2ㆍ10^9 이하다. 그리고 X,Y가 모두 동일한 점은 존재하지 않는다.

출력

각 "P\ i" 쿼리에 대해, i번째 점보다 우상단에 위치한 점들 중 가장 가까운 점이 몇 번째 점인지 출력한다. 점들은 좌표평면에 찍힌 순서대로 번호가 매겨지며 (1부터 시작), 해당하는 점이 없는 경우 "NE"를 출력한다.

예제1

예제2

예제3

예제4

출처

COCI 2006/2007 Contest #4 6번

우상단 최근접 점 3초 128MB