题目描述

给定一个长为 $n$ 的序列，每个位置上给定一个函数 $f_0(0)=c_{i1},f_0(1)=c_{i2}$。

然后定义：$f_1(0)=c_{i2},f_1(1)=c_{i1}$。

定义一个数 $x$ 在二进制下的第 $i$ 位为 $x_i$，其中 $x_0$ 为最低位。

定义一个数 $x$ 在序列位置 $i$ 上的对应结果为 $g_i(x)$，其中 $g_i(x)$ 二进制下第 $j(0\le j\le 29)$ 位为 $f_r(x_j)$（不管最高非零位在哪里，前 $30$ 位均进行 $f_r(x_j)$ 的计算），$r$ 为 $j$ 模 $2$ 后的余数。

每次询问给定一个区间 $[u,v]$。

定义一个数 $x$ 的 “u v 区间对应结果” 为 $g_{u,v}(x)=g_v(\cdots g_{u+1}(g_u(x))\cdots)$。

再给定一个区间 $[l,r]$，求集合 $\{g_{u,v}(l),g_{u,v}(l+1),\cdots ,g_{u,v}(r)\}$ 中的最大值。

输入格式

第一行一个整数 $n,q$，表示序列的长度与询问次数。

接下来 $n$ 行每行两个整数，描述了 $c_{i1},c_{i2}$。保证 $c_{i1},c_{i2}\in\{0,1\}$。

接下来 $q$ 行每行四个非负整数 $u,v,l,r$，表示询问区间 $[u,v]$ 与取值区间 $[l,r]$。

保证 $1\le u,v\le n$。

输出格式

$q$ 行，每行一个整数表示最大值。

样例1

5 5
1 0
0 1
1 1
0 0
0 1
1 1 2 2
2 2 2 2
1 2 2 2
1 3 1 3
2 4 1 2

357913943
715827880
1073741821
1073741823
0

对于第 $1$ 组询问，在询问区间 $[1,1]$ 中，$x$ 仅需进行一次对应，$f$ 的取值如下表所示：

	$a=0$	$a=1$
$f_0(a)$	$1$	$0$
$f_1(a)$	$0$	$1$

在取值区间 $[2,2]$ 中，当 $x=2$ 时，$x$ 的二进制为：

000000000000000000000000000010。

将其按照上表进行映射，得到：

010101010101010101010101010111，

其十进制为 $357913943$。

样例2

见下发文件 ex_2.in/ex_2.out。

该样例满足子任务 1 的数据范围。

样例3

见下发文件 ex_3.in/ex_3.out。

数据范围

子任务编号	分值	特殊性质	依赖
$1$	$20$	$l=1$	无
$2$		$r$ 形如 $2^k-1$
$3$	$15$	$r-l\le 3000,n,q\le 3000$
$4$	$45$	$0\le l,r< 2^{30},n,q\le 10^5$	$1,2,3$