It's funny, the day you lose someone isn't the worst.
At least you've got something to do.
It's the days they stay gone.
小 X 是一位 X 国的附魔师。
自从那场战争爆发到现在,小 X 已经整整一年没有回到 X 国了。战事不断恶化,小 X 与 X 国的故人的联系也如风中残烛一般时断时续。但小 X 却连缅怀过去的时间都没有,肩负着责任的他只能日复一日地战斗着……
今天,小 X 需要进行一场炼金实验。
小 X 面前有 种元素,它们的标号分别为 ,每一种元素 都有一个对应的正整数 ,表示它的魔法强度。每个时刻,小 X 会执行如下操作中的一种:
:发现一种魔法强度为 的新的元素,将其标号为 ,其中 表示当前标号最大的元素的标号。
:对标号在区间 内的元素进行一次实验,计算它们生成的法术的威力值 。
其中 。
显然,对于操作 ,小 X 所操作的 一定可以唯一地写为最简分数 的形式,你需要告诉小 X 的是 和 分别对 取模的值。
从标准输入读入数据。
第一行三个整数 ,分别表示初始时元素的种类数,操作的个数,以及强制在线参数。
接下来一行 个正整数 ,描述初始时各种元素的魔法强度。
接下来 行,每行第一个整数 ,表示当前操作类型。
对于 的操作,接下来输入一个正整数 ,表示新发现的元素的魔法强度。
对于 的操作,接下来输入两个整数 ,表示计算 。
特别地,对于 的数据,令上一次 的操作的答案为 ,所有除 以外的输入数据均需要异或上 ,其中 表示二进制下按位异或。规定:在第一次 的操作之前,。
输出到标准输出。
对于所有 的操作,输出一行两个整数 ,分别表示 最简分数的分子和分母对 取模的结果。
2 3 0
3 4
2 1 2
1 7
2 2 3
13 4
29 7
对于第一个 的操作,。
对于第二个 的操作,。
3 2 0
1 1 998244352
2 2 3
2 1 3
0 998244352
998244352 0
对于第一个 的操作,。
对于第二个 的操作,。
见下发文件。
对于所有测试数据,保证 ,,。
对于 的操作,保证解密后满足 。
对于 的操作,保证解密后满足 ,其中 表示当前标号最大的元素的标号。
详细的数据范围见下表。
测试点编号 | 特殊性质 | |||
---|---|---|---|---|
1 | ||||
2 | ||||
3 | ||||
4 | ||||
5 | 无 | |||
6 | ||||
7 | ||||
8 | ||||
9 | ||||
10 | ||||
11 | ||||
12 | ||||
13 | ||||
14 | ||||
15 | ||||
16 | ||||
17 | 无 | |||
18 | ||||
19 | ||||
20 |
当你做完这题,向 NOI 发起冲刺的时候,不妨回头看看你抛下的一切吧。