수열과 충분한 쿼리

길이 $N$인 수열 $A =\left(A_1, \, A_2, \, \cdots, \, A_N \right)$와 양의 정수 $M$이 주어진다. 또한 다음과 같은 형식의 쿼리 $Q$개가 주어진다.

• i l r

각 쿼리에 대해, 연속 부분수열 $\left(A_i, \, A_{i+1},\, \cdots, \, A_j\right)$에서 $x\in[l,r]$를 만족하는 모든 정수가 각각 $M$번 이상 존재하도록 하는 가장 작은 $j (i \leq j \leq N)$를 출력한다. 그러한 $j$가 존재하지 않으면 -1을 출력한다.

첫 번째 줄에 수열의 길이 $N$과 양의 정수 $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 수열의 원소 $A_1, \, A_2, \, \cdots, \, A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 쿼리의 개수 $Q$가 주어진다.

네 번째 줄부터 총 $Q$개의 줄에 쿼리를 나타내는 세 정수 i l r가 공백으로 구분되어 주어진다.

쿼리가 주어질 때마다 정답을 줄 바꿈으로 구분하여 출력한다.

• $1\le N\le 5 \times 10^5$
• $1\le M\le N$
• $1\le A_i\le 10^9$
• $1\le Q\le 5 \times 10^5$

각 쿼리에 대해 다음이 보장된다.

• $1\le i\le N$
• $1\le l\le r\le 10^9$