Se tienen dos arreglos ~A_1, A_2, \ldots, A_N~ y ~B_1, B_2, \ldots, B_N~, de longitud ~N~, tales que ~A_i \le B_i~ para todo ~0 \le i < n~.

Un intervalo ~[l,r]~, con ~0\le l\le r<n~, se considera maravilloso si es posible transformar el subarreglo ~A[l\dots r]~ en ~B[l\dots r]~ realizando la siguiente operación cero o más veces:

• Sea ~X~ el arreglo actual. Elige dos índices distintos ~i~ y ~j~ dentro de ~[l,r]~ tales que ~X[i]=X[j]~, y aumenta en ~1~ el valor de ~X[i]~ (es decir, ~X[i] \mathrel{\mathop:}= X[i]+1~). Los valores de ~X~ que no se encuentren en las posiciones elegidas permanecen sin cambios.

Se realizarán ~Q~ consultas. Cada consulta consiste en un intervalo ~[L_j,R_j]~, tu tarea es determinar si el intervalo es maravilloso. Imprime ~1~ si lo es y ~0~ en caso contrario.

Entrada

La primera línea contiene dos enteros ~N~ y ~Q~ (~1 \le N, Q \le 250\,000~) ~-~ la longitud de los arreglos y el número de consultas, respectivamente.

Las siguientes ~N~ líneas contienen dos enteros cada una. La ~i~-ésima de estas líneas (~0 \le i < N~) contiene ~A_i~ y ~B_i~ (~1 \le A_i \le B_i \le 10^9~).

Las siguientes ~Q~ líneas contienen dos enteros cada una. La ~j~-ésima de estas líneas (~0 \le j < Q~) contiene ~L_j~ y ~R_j~ (~0 \le L_j \le R_j < N~), que representan cada consulta.

Salida

Imprime ~Q~ enteros en una línea. El ~j~-ésimo entero será ~1~ si el intervalo ~[L_j, R_j]~ de la consulta es maravilloso, o ~0~ en caso contrario.

Subtareas

Esta tarea está compuesta por ~8~ subtareas.

Los puntos de una subtarea se otorgan solo si se aceptan todos los casos de esa subtarea.

Subtarea	Puntos	Restricciones adicionales	Dependencias
~1~	~9~	~1\le N,Q \le 100~; ~1\le B_i \le 100~ para ~0 \le i < N~.	~-~
~2~	~7~	~1\le N,Q \le 2000~; ~A_i = 1~ para ~0 \le i < N~.	~-~
~3~	~16~	~A_i = 1~ para ~0 \le i < N~.	~2~
~4~	~10~	~1\le N,Q \le 2000~.	~1, 2~
~5~	~4~	~1 \le B_i \le 2~ para ~0 \le i < N~.	~-~
~6~	~13~	~1 \le B_i \le 100~ para ~0 \le i < N~.	~1, 5~
~7~	~31~	~1\le B_i \le 250\,000~ para ~0 \le i < N~.	~1, 5, 6~
~8~	~10~	Sin restricciones adicionales.	~1, 2, 3, 4, 5, 6, 7~

Ejemplos

Entrada 1

4 3
2 2
1 1
1 3
2 3
0 1
0 3
1 3

Salida 1

1 1 0

Entrada 2

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

Salida 2

1 1 0 1 0