P16030 [CSPro 23] 箱根山岳险天下

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。 “你知道对长跑选手来说，最棒的赞美是什么吗？” “是‘快’吗？” “不，是‘强’，”清濑说，“光跑得快，是没办法在长跑中脱颖而出的。天候、场地、比赛的发展、体能，还有自己的精神状态——长跑选手必须冷静分析这许多要素，即使面对再大的困难，也要坚忍不拔地突破难关。长跑选手需要的，是真正的‘强’。所以我们必须把‘强’当作最高的荣誉，每天不断跑下去。” 不论阿走或其他房客，全都全神贯注地聆听清濑的话。 “看了你这三个月来的表现，我越来越相信自己没看错人，”清濑接着说，“你很有天分，也很有潜力。所以呢，阿走，你一定要更相信自己，不要急着想一飞冲天。变强需要时间，也可以说它永远没有终点。长跑是值得一生投入的竞赛，有些人即使老了，仍然没有放弃慢跑或马拉松运动。” ——三浦紫苑《强风吹拂》 箱根驿传（正式名称为东京箱根间往复大学驿传竞走）是日本一项在每年 1 月 2-3 日举行的驿站接力赛，由关东学生田径联盟主办，关东的每所高校都有机会参加。在日本，箱根驿传是新年假期必看的比赛，许多家庭会一边吃年糕汤一边欣赏激烈的比赛。 今年，京都大学也想派出长跑队参加箱根驿传，田径部的长跑教练组织起一批预备役运动员，并开展了严苛的训练。

京都大学的训练一共会持续 $m$ 天，在训练过程中正式队员的名单可能发生变化。简单起见，我们约定在且仅在第 $t (1 \leq t \leq m)$ 天结束时，会有以下三种事件之一发生： 1. 有一个学生跑 $10\text{km}$ 的速度达到了正式队员要求，教练将其作为最后一名纳入正式队员的名单中，这个学生的强度为 $x$；或者速度排名在最后一位的正式队员，由于速度过慢，而被从正式队员的名单中淘汰。 - 在训练过程中，我们假定队员的速度的相对排名不会发生变化，与强度无关。 - 严苛的教练制订了残酷的规则：被淘汰的学生虽然依然会跟大家一起训练，但将不能再次加入本年度参加箱根驿传的正式队员的名单中。 2. 由于近日的训练，第 $s$ 天结束时速度排名为 $l$ 至 $r$ 的选手的强度有了变化，变为此前的 $y$ 倍。 3. 教练在深夜想知道近日训练的效果，于是他统计了第 $s$ 天结束时速度排名为 $l$ 至 $r$ 的选手目前（即第 $t$ 天结束时）强度的和。由于这个结果可能很大，方便起见我们只考虑其模 $p$ 的值。 出于学生们的隐私考虑，事件日志有可能会被加密。

从标准输入读入数据。 第一行为三个用空格隔开的整数 $m, p$ 和 $T$。 如果 $T = 0$，事件 1 中 $x = x'$，事件 2 中 $y = y'$；如果 $T = 1$，表示事件日志被加密了，事件 1 中 $x = x' \oplus A$，事件 2 中 $y = y' \oplus A$，其中 $\oplus$ 为按位异或运算，$A$ 为此前最后一次事件 3 所统计出的结果。如果此前没有事件 3 发生，则 $A = 0$。 接下来 $m$ 行，第 $t$ 行表示在第 $t$ 天结束时发生的事件： - $1; x'$：表示事件 1 发生。若 $x > 0$，表示有一个强度为 $x$ 的学生作为最后一名纳入正式队员的名单；若 $x = 0$，表示排名在最后的正式队员被从名单中淘汰。保证有 $0 \leq x' < 2^{30}$。 - $2; s; l; r; y'$：表示事件 2 发生。保证有 $1 \leq s \leq t$, $1 \leq l \leq r \leq n$, $0 \leq y' < 2^{30}$，其中 $n$ 为在第 $s$ 天结束时正式队员的人数。 - $3; s; l; r$：表示事件 3 发生。保证有 $1 \leq s \leq t$, $1 \leq l \leq r \leq n$，其中 $n$ 为在第 $s$ 天结束时正式队员的人数。

输出到标准输出。 对于每一个事件 3，输出一行一个数字，为其所统计出的结果。

### 样例 1 解释 第 $1$ 天结束时，有一个强度为 $7$ 的学生被列为正式队员，我们不妨称他为小津。此时正式队员名单依次为：小津。 第 $2$ 天结束时，有一个强度为 $3$ 的学生被列为正式队员，我们不妨称他为城崎。此时正式队员名单依次为：小津、城崎。 第 $3$ 天结束时，城崎被淘汰了。此时正式队员名单为：小津。 第 $4$ 天结束时，有一个强度为 $4$ 的学生被列为正式队员，我们不妨称他为樋口清太郎。此时正式队员名单依次为：小津、樋口清太郎。 第 $5$ 天结束时，由于近日的训练，第 $4$ 天正式队员名单中第 $1$ 至 $2$ 个人——即小津和樋口清太郎——的强度乘了 $2$，所以，小津的强度达到了 $14$，樋口清太郎的强度达到了 $8$。 第 $6$ 天结束时，教练统计了第 $2$ 天正式队员名单中第 $1$ 至 $2$ 个人——即小津和城崎——当前的强度，小津的强度为 $14$，城崎的强度为 $3$，故统计结果为 $17$，模 $p$ 的值为 $7$。 第 $7$ 天结束时，由于近日的训练，第 $1$ 天正式队员名单中的第 $1$ 个人——即小津——的强度乘了 $3$，所以，小津的强度达到了 $42$。 第 $8$ 天结束时，教练统计了第 $6$ 天正式队员名单中第 $1$ 至 $2$ 个人——即小津和樋口清太郎——当前的强度，小津的强度为 $42$，樋口清太郎的强度为 $8$，故统计结果为 $50$，模 $p$ 的值为 $0$。 ### 子任务 $1 \leq m \leq 3 \times 10^5$, $2 \leq p < 2^{30}$, $T \in {0, 1}$ |测试点 |特殊性质 |$T$| |:-:|:-:|:-:| |$1$ |$m \leq 5000$ |$1$| |$2$ |事件 1 中 $x > 0$ |^| |$3$ |没有事件 2 |^| |$4$ |事件 1 中 $x$ 在 ${0, 1}$ 中随机选取 |$0$| |$5$ |$r - l \leq 10$ |^| |$6$ | ^ |$1$| |$7, 8$ | 无 |$0$| |$9, 10$ | ^ |$1$| 每个测试点占 $10$ 分。