U137981.食堂日志

明德大学第三食堂的经理老周有一个习惯：每天打烊后，他都会在一个本子上记下两件事——今天一共卖出了多少份饭，以及今天有哪几个档口开了门。

这个本子记了整整 $n$ 天。学期末要写总结报告，校长、后勤处和采购科轮番来问他各种各样的问题，而且每次问的都是「第 $l$ 天到第 $r$ 天之间」的情况。老周翻本子翻到手软，于是找到了正在学信息学的你。

食堂一共有 $m$ 个档口，编号为 $0,1,\dots,m-1$。日志记录了连续 $n$ 天的情况：

• 第 $i$ 天卖出了 $a_i$ 份饭；
• 第 $i$ 天开门的档口集合用一个整数 $b_i$ 表示：把 $b_i$ 写成二进制后，若第 $k$ 位（从低位起，最低位为第 $0$ 位）为 $1$，则表示 $k$ 号档口这天开了门，否则表示这天没开。

例如 $m=4$、$b_i=11$ 时，$11$ 的二进制是 $1011$，说明这天 $0,1,3$ 号档口开着，$2$ 号档口没开。

现在有 $q$ 个询问，每个询问给出一个区间 $[l,r]$（表示第 $l$ 天到第 $r$ 天，含两端）和一个操作类型：

• 操作 $1$（全勤档口）：这段时间里每一天都开门的档口有多少个？
• 操作 $2$（三天打鱼）：这段时间里开过门、但没有天天开门的档口有多少个？
• 操作 $3$（食材包规格）：采购科想用一种统一规格的食材包，每包恰好能做出 $k$ 份饭。要求这段时间里每一天的销量都能由整数包食材恰好做出（食材包不能拆开，也不能跨天使用），求 $k$ 最大是多少。
• 操作 $4$（忙闲差）：这段时间里最忙的一天比最闲的一天多卖出多少份饭？

请你对每个询问输出答案。

第一行三个整数 $n,m,q$，分别表示天数、档口数量和询问数量。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每天卖出的份数。

第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$，表示每天开门的档口集合。

接下来 $q$ 行，每行三个整数 $\mathit{op},l,r$，表示一个操作类型为 $\mathit{op}$、区间为 $[l,r]$ 的询问。

共 $q$ 行，每行一个整数，依次表示每个询问的答案。

样例解释 #1

六天的日志如下（$m=4$，档口编号 $0\sim 3$）：

天	卖出份数 $a_i$	$b_i$	二进制	开门的档口
$1$	$12$	$11$	$1011$	$0,1,3$
$2$	$18$	$7$	$0111$	$0,1,2$
$3$	$24$	$3$	$0011$	$0,1$
$4$	$6$	$15$	$1111$	$0,1,2,3$
$5$	$30$	$6$	$0110$	$1,2$
$6$	$15$	$3$	$0011$	$0,1$

• 第 $1$ 个询问：第 $2\sim 4$ 天中，$0$ 号和 $1$ 号档口天天都开，答案为 $2$。
• 第 $2$ 个询问：第 $2\sim 4$ 天中开过门的档口是 $0,1,2,3$ 共 $4$ 个，其中天天开门的有 $2$ 个，所以时开时关的有 $4-2=2$ 个。
• 第 $3$ 个询问：$\gcd(12,18,24)=6$，每包做 $6$ 份饭时，三天分别用 $2,3,4$ 包，恰好用完。
• 第 $4$ 个询问：前三天最多卖 $24$ 份，最少卖 $12$ 份，相差 $12$。
• 第 $5$ 个询问：六天里只有 $1$ 号档口一天没落下，答案为 $1$。
• 第 $6$ 个询问：$\gcd(6,30,15)=3$。

数据范围与约定

对于全部数据，保证：

$1\le n\le 10^5, 1\le q\le 10^5, 1\le m\le 30$

$1\le a_i\le 10^9, 0\le b_i<2^m, \mathit{op}\in\{1,2,3,4\}, 1\le l\le r\le n$

注意 $b_i$ 可能为 $0$，即某一天可能所有档口都没开门。

本题共 $20$ 个测试点，每个测试点 $5$ 分。各测试点的额外限制如下：

测试点编号	$n$	$q$	特殊性质
$1\sim 2$	$\le 100$	$\le 100$	无
$3\sim 5$	$\le 2000$	$\le 2000$	无
$6\sim 7$	$\le 10^5$	$\le 200$	无
$8\sim 10$	$\le 10^5$	$\le 10^5$	只含操作 $1$ 和操作 $2$
$11\sim 13$	$\le 10^5$	$\le 10^5$	只含操作 $3$
$14\sim 15$	$\le 10^5$	$\le 10^5$	只含操作 $4$
$16\sim 20$	$\le 10^5$	$\le 10^5$	无