Eugeny has array $*a* = *a*_{1}, *a*_{2}, ..., *a*_{*n*}$, consisting of $*n*$ integers. Each integer $*a*_{*i*}$ equals to -1, or to 1. Also, he has $*m*$ queries:

• Query number $*i*$ is given as a pair of integers $*l*_{*i*}$, $*r*_{*i*}$ $(1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n*)$.
• The response to the query will be integer $1$, if the elements of array $*a*$ can be rearranged so as the sum $*a*_{*l*_{*i*}} + *a*_{*l*_{*i*} + 1} + ... + *a*_{*r*_{*i*}} = 0$, otherwise the response to the query will be integer $0$.

Help Eugeny, answer all his queries.

Input

The first line contains integers $*n*$ and $*m*$ $(1 ≤ *n*, *m* ≤ 2·10^{5})$. The second line contains $*n*$ integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ $(*a*_{*i*} =$-$1, 1)$. Next $*m*$ lines contain Eugene's queries. The $*i*$-th line contains integers $*l*_{*i*}, *r*_{*i*}$ $(1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n*)$.

Output

Print $*m*$ integers — the responses to Eugene's queries in the order they occur in the input.