题目描述

这是一道传统题。

这题数据应该比较水，大家可以试试写乱搞。

小青鱼给你一个长度 $n$ 的序列，每个位置 $i$ 有权值 $a_i$ 和 $b_i$，其中 $b_i$ 只能是 0 或 1，支持两种类型的操作：

1. 给定 $r$，将 $b_1,b_2,\ldots,b_r$ 全部异或 1。
2. 给定 $l,r$，查询 $\min(|a_i-a_j|)$，满足 $l\le i,j\le r$ 且 $i\ne j$ 且 $b_i=b_j$。如果不存在满足条件的二元组 $(i,j)$，则本次询问的答案为 0。

本题强制在线，每次操作输入的 $l,r$ 都需要与上一次 2 操作的答案对 $n$ 取模后的结果做异或运算。如果上一次没有 2 操作，则认为上一次的答案是 0。

输入格式

第一行两个整数 $n,m$（$1\le n\le 10^5$，$1\le a_i\le 10^{18}$，$1\le m\le 2\times 10^5$）。

第二行 $n$ 个整数，依次表示 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^{18}$）。

第三行 $n$ 个整数，依次表示 $b_1,b_2,\ldots,b_n$（$0\le b_i\le 1$）。

之后 $m$ 行，每行输入的第一个整数 $op$ 表示操作类型：

• 如果 $op=1$，则接下来输入 $r$，表示进行一次第一种类型的操作；
• 如果 $op=2$，则接下来输入 $l,r$，表示进行一次第二种类型的操作。

输出格式

对于每个第 2 类型的操作，输出一行一个数表示答案。

样例输入

10 10
765043762025233898 121275569459285310 527307592414888835 846940445346968938
254143821609554581 954919226849600292 157902796240270318 607450804939563478
889306955896231283 4685498002534601
0 0 1 0 1 0 1 0 1 0
1 5
2 3 8
2 11 9
1 14
2 2 13
2 5 1
2 2 3
2 3 7
2 7 3
1 1

样例输出

80143212524674643
602765306937028877
153217298237735717
273163770805334254
0
273163770805334254
273163770805334254

数据范围

• 对于 10% 的数据，满足 $n,m\le 100$。
• 对于另外 10% 的数据，满足 $n,m\le 5000$。
• 对于另外 30% 的数据，满足 $n,m\le 50000$。
• 对于另外 20% 的数据，满足 $a_i\le 10^5$。
• 对于 100% 的数据，满足 $1\le n\le 10^5$，$1\le m\le 2\times 10^5$，$1\le a_i\le 10^{18}$，强制在线解密后 $1\le l\le r\le n$。

特别地，每组数据中保证最多有 $2\times 10^4$ 次第 1 类型的操作。