Descripción

¡Corre! Como te quedaste dormido el día del examen y llegaste tarde, solo tienes 10 minutos para resolver el siguiente problema de tu clase de Fundamentos de Programación.

Se te da un arreglo \(A_1, A_2, \cdots , A_N\). Debes responder \(Q\) consultas del siguiente tipo:

• Si cambiamos todos los elementos en el rango \(A_L, A_{L+1}, \cdots , A_R\) del arreglo al valor \(K\), ¿la suma de todo el arreglo será impar?

Ten en cuenta que las consultas son independientes y no afectan a las consultas futuras.

Entrada

La entrada contiene múltiples casos de prueba.

La primera línea contiene el número de casos de prueba \(T (1 \leq T \leq 10^4)\).

La descripción de los casos de prueba es la siguiente:

• La primera línea de cada caso de prueba contiene dos enteros \(N\) y \(Q\) \((1 \leq N, Q \leq 2 · 10^5)\), donde \(N\) es la longitud del arreglo y \(Q\) es el número de consultas.
• La segunda línea de cada caso de prueba contiene \(N\) enteros \(A_i (1 \leq A_i \leq 10^9)\), que representan el arreglo \(A\).
• Las siguientes \(Q\) líneas de cada caso de prueba contienen tres enteros \(L\), \(R\) y \(K\) \((1 \leq L \leq R \leq N, 1 \leq K \leq 10^9)\), que representan las consultas.

Se garantiza que la suma de \(N\) sobre todos los casos de prueba no excede \(2 · 10^5\), y que la suma de \(Q\) no excede \(2 · 10^5\).

Salida

Para cada consulta, imprime 'SI' si la suma de todo el arreglo se vuelve impar, y 'NO' en caso contrario.

Ejemplo

Entrada

2
5 5
2 2 1 3 2
2 3 3
2 3 4
1 5 5
1 4 9
2 4 3
10 5
1 1 1 1 1 1 1 1 1 1
3 8 13
2 5 10
3 8 10
1 10 2
1 9 100

Salida

SI
SI
SI
NO
SI
NO
NO
NO
NO
SI

Notas

Para el primer caso de prueba:

• Si los elementos en el rango \((2,3)\) se cambian a \(3\), el arreglo se convertiría en \({2,3,3,3,2}\), la suma sería \(2+3+3+3+2=13\), que es impar, por lo que la respuesta es 'SI'.
• Si los elementos en el rango \((2,3)\) se cambian a \(4\), el arreglo se convertiría en \({2,4,4,3,2}\), la suma sería \(2+4+4+3+2=15\), que es impar, por lo que la respuesta es 'SI'.
• Si los elementos en el rango \((1,5)\) se cambian a \(5\), el arreglo se convertiría en \({5,5,5,5,5}\), la suma sería \(5+5+5+5+5=25\), que es impar, por lo que la respuesta es 'SI'.
• Si los elementos en el rango \((1,4)\) se cambian a \(9\), el arreglo se convertiría en \({9,9,9,9,2}\), la suma sería \(9+9+9+9+2=38\), que es par, por lo que la respuesta es 'NO'.
• Si los elementos en el rango \((2,4)\) se cambian a \(3\), el arreglo se convertiría en \({2,3,3,3,2}\), la suma sería \(2+3+3+3+2=13\), que es impar, por lo que la respuesta es 'SI'.