题目描述

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 面前有 $N$ 种元素，它们的标号分别为 $1,2,\dots,N$，每一种元素 $i$ 都有一个对应的正整数 $a_i$，表示它的魔法强度。每个时刻，小 X 会执行如下操作中的一种：

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

• $2$ ：对标号在区间 $[l,r]$ 内的元素进行一次实验，计算它们生成的法术的威力值 $f(a_l,a_{l+1},\dots,a_r)$。

其中 $f(x)=x,f(a_0,a_1,a_2,\dots,a_n)=a_0+\frac{1}{f(a_1,a_2,\dots,a_n)}\ (n\geq1)$。

显然，对于操作 $2$，小 X 所操作的 $f(a_l,a_{l+1},\dots,a_r)$ 一定可以唯一地写为最简分数 $\frac{x}{y}$ 的形式，你需要告诉小 X 的是 $x$ 和 $y$ 分别对 $998244353$ 取模的值。

输入格式

从标准输入读入数据。

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

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

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

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

对于 $opt=2$ 的操作，接下来输入两个整数 $l,r$ ，表示计算 $f(a_l,a_{l+1},\dots,a_r)$ 。

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

输出格式

输出到标准输出。

对于所有 $opt=2$ 的操作，输出一行两个整数 $Ansx,Ansy$，分别表示 $f(a_l,a_{l+1},\dots,a_r)$ 最简分数的分子和分母对 $998244353$ 取模的结果。

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 \leq N,M \leq 5\times10^5$，$Type\in\{0,1\},opt\in\{1,2\}$，$1\leq a_i\leq 998244352$。

对于 $opt=1$ 的操作，保证解密后满足 $1\leq x\leq 998244352$。

对于 $opt=2$ 的操作，保证解密后满足 $1\leq l\leq r\leq Max$，其中 $Max$ 表示当前标号最大的元素的标号。

详细的数据范围见下表。

测试点编号	$Type$	$N$	$M$	特殊性质
1	$=0$	$\leq 5$	$\leq 10$	$a_i,x\leq50,opt=2$
2		$\leq 50$	$\leq 100$
3				$a_i,x\leq50$
4
5		$\leq 2\times 10^3$	$\leq 3\times 10^3$	无
6
7
8		$\leq 5\times 10^4$	$\leq 10^5$
9
10
11		$\leq 5\times 10^5$	$\leq 5\times 10^5$
12
13	$=1$	$\leq 10^5$		$l=1$
14
15		$\leq 5\times 10^5$
16
17		$\leq 10^5$		无
18
19		$\leq 5\times 10^5$
20

提示

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