Tienes un array con ~N~ enteros ~a_i~. Quieres (para resolver el problema) saber el menor ~i~ ~(1 \le i \le N)~, tal que en los ~i~ primeros elementos del array hayan ~X~ elementos en el intervalo cerrado ~[L, R]~, es decir que la cantidad de indices ~j~, tal que ~1 \le j \le i~ y ~L \le aj \le R~, es igual a ~X~ o ~N+1~ si no existe ningún ~i~ que lo cumpla. Claramente vamos a hacer muchas preguntas, ~Q~ para ser precisos.

Entrada

En la primera linea ~N~ y ~Q~ separados por un espacio, las siguientes ~N~ lineas contienen los elementos del array, las siguientes ~Q~ lineas contienen ~L_i~ ~R_i~ ~X_i~ separados por espacios, mas o menos como en el ejemplo de allá abajo.

Salida

~Q~ lineas: la ~i-esima~ linea contiene la respuesta de la ~i-esima~ pregunta.

Ejemplo entrada

5 4
1
2
3
4
5
1 5 1
1 5 2
1 2 3
2 4 2

Ejemplo salida

1
2
6
3

Restricciones

· ~1 \le a_i, L_i, R_i \le 10^9~.

· ~1 \le X \le N~.

·Subtarea ~1~ ~N~, ~Q = 5000~ ~10~ puntos.

·Subtarea ~2~ ~N~ ,~Q = 30000~ ~30~ puntos.

·Subtarea ~3~ ~N~, ~Q = 100000~ ~60~ puntos.