#P17740. 小A的白日梦

小A的白日梦

题目描述

小A做了一个白日梦,他梦到自己成为了世界上最富有的人。但没过多久,小A就发现富有的生活也非常无聊,他决定把他的钱财散发给其他人。

小A决定分发钱财的人一共有nn个,他们排成了一排。一开始,这些人都很穷,没有任何钱。每一次,小A会给连续一段人每人发kk元钱。小A认为学会分享是很重要的,所以有时小A会让第ll个人到第rr个人交换拥有的钱,具体交换方法为,对于所有非负整数kk使得l+k<r−kl+k<r-k,交换l+kl+k和r−kr-k的钱。当然,为了了解现状,小A还会询问连续一段人的钱财总和。

小A梦里的人太多了,为了更好地做白日梦,小A希望你可以写一个程序帮他完成统计。

输入格式

从标准输入读入。

第一行三个整数n,m,typn,m,typ,表示人数,操作数,数据类型。

接下来mm行,每行先有一个整数optopt

如果opt=0opt=0,接着3个整数l,r,kl,r,k,表示给第ll到第rr个人每人kk元钱。

如果opt=1opt=1,接着2个整数l,rl,r,表示交换第ll到第rr个人的钱,具体交换规则见题目描述。

如果opt=2opt=2,接着2个整数l,rl,r,表示询问第ll到第rr个人的总钱数。

特殊的,如果typ=1typ=1,那么小A的操作会根据询问到的结果来改变。具体的,除了optopt以外的每一个数都要异或上一个答案,初始时上一个答案为0。

输出格式

输出到标准输出。

对于每一个询问,输出答案。

样例

样例输入 1

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

样例输出 1

2
4

数据范围

$n\le 10^9, m\le 2.5\times10^5,typ\in \{0,1\},k \le 10000,1\le l\le r \le n,opt\in \{0,1,2\}$

注意:当typ=1typ=1时,读入的l,r,kl,r,k可能超过int的存储范围。

subtask 1 21pts n≤1000,m≤1000n\le 1000,m\le 1000

subtask 2 17pts n≤2×105n\le 2\times 10^5

subtask 3 23pts 对于所有opt=1opt=1,存在一个kk使得r−l=2k,rmod  2k=0,lmod  2k=0r-l=2^k,r \mod 2^k=0,l \mod 2^k=0

subtask 4 11pts typ=0typ=0

subtask 5 16pts m≤105m\le 10^5

subtask 6 12pts 无特殊限制