식물 비교

식물학자 헤이즐이 싱가포르 식물원의 특별 전시회를 방문했다. 전시에는 높이가 서로 다른 $n$개의 식물이 원형으로 놓여 있다. 식물에는 시계 방향으로 $0$부터 $n-1$까지 번호가 붙어 있고, 식물 $n-1$의 옆은 식물 $0$이다.

각 식물 $i$ ($0 \leq i \leq n-1$)에 대해 헤이즐은 식물 $i$를 시계 방향으로 바로 다음에 오는 $k-1$개의 식물과 하나씩 비교했다. 그리고 그중 식물 $i$보다 키가 큰 식물의 개수를 $r[i]$에 적었다. 따라서 각 $r[i]$ 값은 연속한 $k$개 식물의 상대적 높이에 따라 정해진다.

예를 들어 $n=5$, $k=3$, $i=3$인 경우를 보자. 식물 $3$에서 시계 방향으로 다음 $k-1=2$개의 식물은 식물 $4$와 식물 $0$이다. 식물 $4$가 식물 $3$보다 크고 식물 $0$이 식물 $3$보다 작으면, 헤이즐은 $r[3]=1$을 적는다.

헤이즐이 모든 $r[i]$를 정확히 기록했다고 가정해도 된다. 이 값과 맞는, 높이가 서로 다른 배치가 적어도 하나 존재한다.

여러분은 $q$쌍의 식물에 대해 높이를 비교해야 한다. 전시장에는 들어갈 수 없고, 얻을 수 있는 정보는 헤이즐의 노트에 적힌 $k$ 값과 수열 $r[0], \ldots, r[n-1]$뿐이다.

서로 다른 두 식물 $x$와 $y$의 쌍마다 다음 중 어느 경우인지 판단하라.

• 식물 $x$가 식물 $y$보다 확실히 크다: $r$과 맞는 모든 높이 배치 $h[0], \ldots, h[n-1]$에서 $h[x] > h[y]$이다.
• 식물 $x$가 식물 $y$보다 확실히 작다: 맞는 모든 배치에서 $h[x] < h[y]$이다.
• 판단할 수 없다: 위 두 경우 중 어느 쪽도 아니다.

$2 \leq k \leq n \leq 200000$

$1 \leq q \leq 200000$

$0 \leq r[i] \leq k-1$ (모든 $0 \leq i \leq n-1$에 대해)

$0 \leq x < y \leq n-1$

$r$과 맞는, 높이가 서로 다른 배치가 적어도 하나 존재한다.