小马宝莉的一员小马丫丫是一个爱好多项式的小马，他曾经尝试过将多项式与许许多多 OI 的其他知识点结合，而今天他想要将多项式与字符串结合。
小马丫丫定义，如果一个 $n$ 次多项式 $F$ 满足 $[x^i]F(x)=[x^{n-i}]F(x)$ ，则我们称其为回文多项式，其中 $[x^i]F(x)$ 表示多项式 $F(x)$ 的 $i$ 次项系数。特别地，常数也是回文多项式。小马丫丫惊奇的发现：
- 回文多项式 $F$ 和回文多项式 $G$ 相乘得到的多项式 $H$ ，他也是一个回文多项式。
- 回文多项式 $F$ 和非回文多项式 $G$ 相乘得到的多项式 $H$ ，他并不是一个回文多项式。
作为多项式爱好者，小马丫丫自然收集了许多的多项式，他拿出了 $n$ 个 $k_i$ 次多项式 $F_i(x)=\sum_{j=0}^{k_i}a_jx^j$ 排成一排。保证 $a_{k_i}\ne 0$ 。他想让你帮他查询这个多项式序列。
具体的，存在 $q$ 个操作询问 l r ，告诉小马丫丫区间 $[l,r]$ 的多项式相乘之后是否是一个回文多项式。
输入格式
第一行两个整数 $n,q$ 。
接下来 $n$ 行，每行第一个数为整数 $k_i$ 。接下来 $k_i$ 个整数 $a_{j}$ 。
在接下来 $q$ 行表示 $q$ 个操作，每行有两个整数 $l,r$ ，表示询问的区间。
输出格式
对于每一个询问，输出一行一个 0/1 表示 非/是 回文多项式。
样例数据
样例输入
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)： 无特殊限制。
对于 $100\%$ 的数据，保证 $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$ 。