A. 单枪匹马

小 X 是一位 X 国的附魔师。

自从那场战争爆发到现在，小 X 已经整整一年没有回到 X 国了。战事不断恶化，小 X 与 X 国的故人的联系也如风中残烛一般时断时续。但小 X 却连缅怀过去的时间都没有，肩负着责任的他只能日复一日地战斗着……

今天，小 X 需要进行一场炼金实验。

小 X 面前有 种元素，它们的标号分别为 ，每一种元素 都有一个对应的正整数 ，表示它的魔法强度。每个时刻，小 X 会执行如下操作中的一种：

• ：发现一种魔法强度为 的新的元素，将其标号为 ，其中 表示当前标号最大的元素的标号。

• ：对标号在区间 内的元素进行一次实验，计算它们生成的法术的威力值 。

其中 。

显然，对于操作 ，小 X 所操作的 一定可以唯一地写为最简分数 的形式，你需要告诉小 X 的是 和 分别对 取模的值。

从标准输入读入数据。

第一行三个整数 ，分别表示初始时元素的种类数，操作的个数，以及强制在线参数。

接下来一行 个正整数 ，描述初始时各种元素的魔法强度。

接下来 行，每行第一个整数 ，表示当前操作类型。

对于 的操作，接下来输入一个正整数 ，表示新发现的元素的魔法强度。

对于 的操作，接下来输入两个整数 ，表示计算 。

特别地，对于 的数据，令上一次 的操作的答案为 ，所有除 以外的输入数据均需要异或上 ，其中 表示二进制下按位异或。规定：在第一次 的操作之前，。

输出到标准输出。

对于所有 的操作，输出一行两个整数 ，分别表示 最简分数的分子和分母对 取模的结果。

样例输入 1

2 3 0
3 4
2 1 2
1 7
2 2 3

样例输出 1

13 4
29 7

样例说明 1

对于第一个 的操作，。

对于第二个 的操作，。

样例输入 2

3 2 0
1 1 998244352
2 2 3
2 1 3

样例输出 2

0 998244352
998244352 0

样例说明 2

对于第一个 的操作，。

对于第二个 的操作，。

样例 3

见下发文件。

数据范围

对于所有测试数据，保证 ，，。

对于 的操作，保证解密后满足 。

对于 的操作，保证解密后满足 ，其中 表示当前标号最大的元素的标号。

详细的数据范围见下表。

提示

当你做完这题，向 NOI 发起冲刺的时候，不妨回头看看你抛下的一切吧。