문제
정올국은 여러 개의 섬으로 이루어진 섬나라이다. 이 섬들은 수평선 위에 위치해 있다.
각 섬은 높이가 각각 다르다. 정올국의 정책은 다음과 같다: 어떤 섬에 쓰나미가 덮쳐서 침수될 것이 예상되면, 그 섬의 주민들을, 섬의 오른쪽에 있고 높이가 더 높은 가장 가까운 섬으로 대피시킨다.
어떤 섬이 침수되었다고 해서, 그 섬보다 높이가 낮은 섬들이 모두 침수되는건 아니다 (우리는 해면 상승이 아니라 쓰나미를 다루고 있다). 또한, 어떤 섬이 침수되었을 때, 그 섬은 두번다시 복구되지 않는다(즉 더 이상 지도상에 없는 섬이다). 모든 섬은 무한히 많은 주민들을 포용할 수 있다.
기상정보국은 당신에게 다음과 같은 경우에 연락해줄 것이다. - 1) 어떤 섬이 침수되었다. 침수된 섬이 또 침수되었다는 정보가 들어올 수도 있다. - 2) 어떤 섬의 주민들을 대피시켜야 한다. 이 경우에 당신은 국민들에게 이 섬의 주민들이 대피할 섬을 알려주어야 한다. 같은 섬의 주민들을 두 번 이상 피난시켜야 할 수도 있다.
참고로 쓰나미는 x축의 왼쪽이나 오른쪽에서 높은 파도의 형태로 몰려오는 것이 아니라, 하나의 특정 섬을 침수시킬 수 있는 국지성이다. 따라서 기상정보국의 정보는 오직 그 한 섬에 대해서만 유효하고, 그것을 통해 다른 섬의 피해를 추론할 수는 없다.
섬들의 위치와 높이가 각각 주어졌을 때, 기상정보국의 정보를 받아서 2)번과 같은 경우에 주민들이 대피할 섬을 알려 주는 프로그램을 작성하라.
입력
첫째 줄에 n, 섬의 개수가 주어진다. (1 <= n <= 200,000, n은 정수)
다음 n줄에는 섬의 위치와 높이를 나타내는 x_i와 y_i가 공백을 사이에 두고 주어진다. 여기서 (n이 주어진 첫 줄을 배제하고) i번째 줄의 섬은 i번 섬이라고 한다. 한 좌표에 두 섬의 정보가 입력되는 경우는 없다.
다음 줄에 q가 주어진다. q는 기상정보국에 들어오는 정보의 수이다. (1 <= q <= 200,000, q는 정수)
그 다음 q개의 줄에는 정보들이 들어오며, 이 일련의 사건들은 일어난 시간 순으로 들어온다. 정보들은 두 가지 형태 중 하나이다. - d x: x라는 위치에 있는 섬이 침수되었다. - e i: i번 섬의 주민들을 대피시켜야 한다. ( 0 <= x, x_i <= 109) ( 0 <= y <= 1.1*109) (1 <= i <= n) d x의 형태로 들어오는 정보의 경우, x좌표에 섬이 반드시 있음을 보장한다.
출력
e i 형식의 정보가 정보국에 들어올 때마다, i번 섬의 높이보다 높으면서 오른쪽에 있는 가장 가까운 침수되지 않은 섬의 좌표를 출력하라.
만약 그런 섬이 없으면 IMPOSSIBLE 을 출력한다. 만약 i번 섬 자체가 침수된 섬이면 DROWNED를 출력한다.
예제
6
2 3
10 8
9 2
3 1
6 3
12 4
6
e 1
d 10
e 4
d 12
e 3
e 2
10
6
IMPOSSIBLE
DROWNED
로그인해야 코드를 작성할 수 있어요.