原题目名字是“我们仍未知道那天所看见的数据结构的名字”，由于原题目名太长就叫Unknown了……

我们，渐渐地长大了。在这缓缓逝去的季节里，屏幕上闪烁的字符，也在静静地变化着。

那个季节里编写的数据结构，叫什么名字来着呢？

慢慢地，OI渐渐地淡去。而我们则在不断成长，但是那个程序一定仍在某个时空里继续运行着。

Salroey忘了那个数据结构的名字和内容，但她却记得题目，于是她来寻求你的帮助。

有一个元素为向量的序列，下标从1开始，初始时为空，现在你需要支持三个操作：

1.在$S$的末尾添加一个元素$(x,y)$。

2.删除$S$的末尾元素。

3.询问下标在$[l,r]$区间内的元素中，$(x,y) \times S_i$的最大值。

其中$\times$表示向量的叉积，$(x_1,y_1) \times (x_2,y_2) = x_1y_2-x_2y_1$

输入格式

第一行一个整数 $tp$ 表示数据类型，接下来输入多组数据(不超过 $3$ 组)，以 $m=0$ 结束，对于每组数据：

第一行一个整数 $m$ 表示操作数。

接下来行，每行有三种格式：

1 x y 在的末尾添加一个元素 $(x,y)$

2 删除的末尾元素

3 l r x y 询问下标在区间 $[l,r]$ 内的元素中，$(x,y) \times S_i$的最大值。

输出格式

为避免过多输出，你要将所有询问答案对M=998244353取模(数学意义上，取模的结果在[0,M)区间内)，并输出取模后答案的异或和，每组数据一行。

样例一

input

7
6
1 -5 10
3 1 1 7 -9
2
1 2 6
1 -3 5
3 1 2 10 -7
0

output

83

样例二

见样例数据下载。

限制与约定

对于所有数据：

$0 \leq tp \leq 7, 1 \leq m \leq 500000$。

任意时刻 $n \geq 0$， $n$ 为当前序列长度。

1操作个数不超过$300000$，且满足 $-10^9 \leq x \leq 10^9; 1 \leq y \leq 10^9$。

3操作个数不超过$300000$，且满足 $1 \leq x \leq 10^9; -10^9 \leq y \leq 10^9$。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载

IOI赛制

本题在考试时排行榜上显示的成绩即为最终评测结果。