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.

输入描述:

The first line contains integers n and m(1 ≤ n, m ≤ 2·105). The second line contains n integers a1, a2, ..., an(ai = -1, 1). Next m lines contain Eugene's queries. The i-th line contains integers li, ri(1 ≤ li ≤ ri ≤ n).

输出描述:

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