#P11735. [集训队互测 2015] 胡策的数列
[集训队互测 2015] 胡策的数列
题目描述
在 OI 界,有一个无人不知无人不晓,OI 水平前无古人后无来者的胡策,江湖人称一眼秒题胡大爷!
今天胡策正在研究一个远古传下来的数列:,数列的第 项为 。这个数列有特别的性质,对于 有:。因为流传的时间太过久远, 和 的值都已经看不清了,但是在最后还记载着,这个数列有一个特别的性质:对于任意的 ,都有 。
然而胡策已经看穿了一切:对于任意一个正数 ,满足 的数列 是唯一的!但是,他想拿这个问题考一考拜胡策为师的你。
具体来说,胡策会给你一个长度为 的表格,一开始每个格子都写着 。有时他会让你将 时的数列 从第 项到第 项的值分别写入表格中第 到第 格(覆盖原有的值),有时他会询问表格中某一段连续的格子中的数的和。
当然,作为胡策的弟子,你必须在胡策提出一个询问的时候马上作出回应。
因为这是一个远古的问题,胡策只给了你一台远古的计算机,它只有 64MB 的内存。
输入格式
第一行两个正整数 。分别表示表格的长度和操作个数。
接下来 行,每行描述一个操作。每行的第一个整数 描述了操作的类型, 表示是修改操作, 表示是询问操作。
如果是修改操作,接下来有四个整数 ,意义如上所述。
如果是询问操作,接下来有两个整数 ,意义如上所述。
由于胡策需要确定你是在线回答他的问题,输入中的 是加密了的。于是你需要把输入中的 分别异或 来得到实际的 。 表示上一次询问操作的答案,初始为 。保证实际的 满足 。
输出格式
对每个询问操作输出一行,表示询问的答案。
答案一定能写成 的形式,其中 是互质的整数,且 。为了避免分数,你只用输出一个介于 到 之间的整数 满足 来表示答案。显然在本题中,这样的 是唯一的。
3 3
1 1 3 2 3
1 2 2 4 5
2 1 3
867840008
1000000000 3
1 1 12450 6666666 23333333
1 6666 99999 2333 44444
2 1 1000000000
431287288
提示
数据范围
- 对于 20% 的数据,。
- 对于 50% 的数据,。
- 对于 100% 的数据,,,,。