409717: GYM103698 G Palinomial

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 l r. You need to tell Pony Yaya whether the multiplication of polynomials in the interval $$$[l, r]$$$ is a palindromic polynomial.

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.

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

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

0
0
1
0

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$$$ .