#P17740. 小A的白日梦
小A的白日梦
题目描述
小A做了一个白日梦,他梦到自己成为了世界上最富有的人。但没过多久,小A就发现富有的生活也非常无聊,他决定把他的钱财散发给其他人。
小A决定分发钱财的人一共有个,他们排成了一排。一开始,这些人都很穷,没有任何钱。每一次,小A会给连续一段人每人发元钱。小A认为学会分享是很重要的,所以有时小A会让第个人到第个人交换拥有的钱,具体交换方法为,对于所有非负整数使得,交换和的钱。当然,为了了解现状,小A还会询问连续一段人的钱财总和。
小A梦里的人太多了,为了更好地做白日梦,小A希望你可以写一个程序帮他完成统计。
输入格式
从标准输入读入。
第一行三个整数,表示人数,操作数,数据类型。
接下来行,每行先有一个整数
如果,接着3个整数,表示给第到第个人每人元钱。
如果,接着2个整数,表示交换第到第个人的钱,具体交换规则见题目描述。
如果,接着2个整数,表示询问第到第个人的总钱数。
特殊的,如果,那么小A的操作会根据询问到的结果来改变。具体的,除了以外的每一个数都要异或上一个答案,初始时上一个答案为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\}$
注意:当时,读入的可能超过int的存储范围。
subtask 1 21pts
subtask 2 17pts
subtask 3 23pts 对于所有,存在一个使得
subtask 4 11pts
subtask 5 16pts
subtask 6 12pts 无特殊限制