A member of My Little Pony, Pony Yaya, is a pony who loves polynomials. He once tried to combine polynomials with many other OI techniques, and today he wants to combine polynomials with strings.

Pony Yaya defines that, if an $n$-degree polynomial $F$ satisfies $[x^i]F(x)=[x^{n-i}]F(x)$ , then we will call it a palindromic polynomial, where $[x^i]F(x)$ represents the coefficient of the $i$-th degree of polynomial $F(x)$. In particular, the constants are also palindromic polynomials. Pony Yaya is surprised to find:

• The polynomial $H$ obtained by multiplying the palindromic polynomial $F$ and the palindromic polynomial $G$ is also a palindromic polynomial.
• The polynomial $H$ obtained by multiplying the palindromic polynomial $F$ and the non-palindromic polynomial $G$ is not a palindromic polynomial.

As a polynomial lover, Pony Yaya has collected a lot of polynomials, and he put $n$ $k_i$-degree polynomials $F_i(x)=\sum_{j=0}^{k_i}a_jx^j$ in a sequence. It is guaranteed that $a_{k_i} \ne 0$. He wants you to help him do some queries on this polynomial sequence.

Specifically, there are $q$ queries in the form of \texttt{l r}. You need to tell Pony Yaya whether the multiplication of polynomials in the interval $[l, r]$ is a palindromic polynomial.

Input

The first line contains two integers $n, q$.

For the following $n$ lines, the first number of each line is an integer $k_i$, and the following $k_i$ integers are the coefficients $a_{j}$ of the $i$-th polynomial.

For the following $q$ lines, each line contains two integers $l, r$, representing the $q$-th query.

Output

For each query, output $0$ if the result is not a palindromic polynomial, and $1$ otherwise.

Example

Input

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

Output

0
0
1
0

Subtasks

Subtask 1 (13pts): $q,\sum k\le 500$ .

Subtask 2 (11pts): $q\le 10$ .

Subtask 3 (19pts): $k_i\le 1$ .

Subtask 4 (23pts): $k_i\le 3$ .

Subtask 5 (34pts): No special restrictions.

For $100\%$ data,it's guaranteed that $1\le n\le 10^5,1\le q\le 10^5,1\le x,l,r\le n,0\le a_i < 10^9,\sum k\le 5\times 10^5$ .