题目背景

物是人非事事休，欲语泪先流。

题目描述

弗雷兹在 C 市有一个玩具店，店里有 $n$ 种玩具，编号依次为 $1,2,\dots, n$，编号为 $i$ 的玩具的单价为 $c_i$ 元，一个该玩具提供的愉悦度为 $v_i$ 。

突然有一天，C市来了 $m$ 个小朋友。据可靠消息，这些小朋友会在一些时刻一起来店里买东西，其中第 $i$ 个小朋友每次都会带 $i$ 元（ $1\leq i\leq m$ ）。

由于某些玩具特别优秀，所以每次小朋友们都会在特定的编号范围内挑选玩具。

除此之外，由于小朋友们在一年前的清华校赛中就愉悦得无法自拔，所以弗雷兹放弃了对他们的治疗，于是小朋友们就可以无限制地购买玩具了。也就是说，对于任意玩具，每个小朋友在每次的购买件数都可以是任意的非负整数。

时代飞速发展，玩具的受欢迎程度和价格也会随着时代的发展而改变。

为了方便你处理这些信息，Yazid 进行了整理，发现这些日子里，弗雷兹的玩具商店里共发生了 $Q$ 个事件。

对于每个事件，都有 $3$ 个基本参数 $op,l,r$ 。其中 $op$ 为 $1$ 至 $3$ 之间的整数，代表了事件的类别：

1. 对于 $op=1$ 的事件，Yazid 还会给你一个额外参数 $d$ ，表示这是一个价格调整事件：将编号在区间 $[l,r]$ 内的玩具的单价 $c$ 全部增加 $d$ 元。为了防止单价超过 $m$ 元导致玩具永远无法被小朋友们购买，弗雷兹会将所有超过 $m$ 的单价减去 $m$。（保证 $d$ 为不超过 $m$ 的正数）

2. 对于 $op=2$ 的事件，Yazid还会给你一个额外参数 $b$ ，表示这是一个愉悦修正事件：将编号在区间 $[l,r]$ 内的玩具的愉悦度 $v$ 全部增加 $b$ 。（需要注意这里的 $b$ 可能是负数）

3. 对于 $op=3$ 的事件，表示购买事件：所有的 $m$ 个小朋友来到弗雷兹的玩具商店，在编号范围在 $[l,r]$ 内的玩具中进行随意地购买。

现在，对于每一次的购买事件，你想知道：

1. 所有小朋友所能获得的最大愉悦度之和。

2. 所有小朋友所能获得的最大愉悦度的异或和（异或运算是 $\mathrm{xor}$ 运算，即 C++/Java/Python 中的 ^ 运算）。

输入格式

• 第 $1$ 行 $2$ 个正整数 $n,m$，分别表示玩具数量、以及小朋友的数量。

• 第 $2$ 行 $n$ 个正整数 $c_1,\dots,c_n$，依次描述各玩具的单价。

• 第 $3$ 行 $n$ 个正整数 $v_1,\dots,v_n$，依次描述各玩具的愉悦度。

• 第 $4$ 行 $1$ 个非负整数 $Q$，表示事件的数量。

• 接下来 $Q$ 行依次描述所有事件，每行描述一个事件。每行的开头是 $3$ 个整数 $op,l,r$，意义见题目描述。

  • 如果 $op=1$，接下来跟随 $1$ 个该事件的额外参数（整数） $d$，意义见题目描述。

  • 如果 $op=2$，接下来跟随 $1$ 个该事件的额外参数（整数） $b$，意义见题目描述。

  • 如果 $op=3$，接下来无任何额外参数。

  • 保证 $1\leq l\leq r\leq n$。

对于每一行，如果包含多个数，则用单个空格将它们隔开。

输出格式

• 对于每个购买事件，输出一行 $2$ 个用空格隔开的整数，依次表示所有小朋友所能获得的最大愉悦度之和、以及所有小朋友所能获得的最大愉悦度的异或和。

4 10
1 6 10 2
100 2333 666 300
7
3 1 4
3 1 3
1 2 4 1
3 1 4
2 2 3 -1000
2 2 3 -600
3 2 4

15165 2865
14165 2169
36630 798
4899 1273

提示

样例解释

对于第 $1$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$100,300,400,600,700,2333,2433,2633,2733,2933$。

对于第 $2$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$100,200,300,400,500,2333,2433,2533,2633,2733$。

对于第 $3$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$666,1332,1998,2664,3330,3996,4662,5328,5994,6660$。

对于第 $4$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$0,0,300,300,300,600,733,733,900,1033$。

根据这些信息，你将很容易计算出答案。

数据范围

保证 $1\le n\leq 200,000$，$1\le m\leq 60$，$0\le Q\leq 30,000$。

保证 $1\leq c_i,d\leq m$。

保证 $0\leq v_i\leq 10^7$，$\left| b\right|\leq 10^3$。

提示

这个提示本不该有，但善良的出题人还是想提醒你：所有小朋友所能获得的最大愉悦度之和有可能超过 $32$ 位有符号整数的范围。

版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。