E-斐波那契的压迫_牛客练习赛133

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 输出斐波那契数列的前 $5$ 项？

$\hspace{15pt}$ 不会做也没关系，我们这里有一个更简单的关于斐波那契数列的问题，你能够解决她吗？

$\hspace{15pt}$

$\hspace{15pt}$ 记斐波那契数列的前 $x$ 个数为 $F_1,F_2,\cdots,F_x$ ，我们回忆斐波那契数列的定义如下：

$\begin{cases}<br />F_1=1 \\<br />F_2=1 \\<br />F_n=F_{n-1}+F_{n-2} & n > 2<br />\end{cases}$

$\hspace{15pt}$ 现在，小姬需要你写一种数据结构来维护一个数列，数列下标从 $1$ 开始。你需要处理 $n$ 次操作，这些操作有以下五种类型的操作：
${\hspace{20pt}}_\texttt{1.}\,$ 在数列后方插入 $F_1 \sim F_x$ 。
${\hspace{20pt}}_\texttt{2.}\,$ 在数列前方插入 $F_1 \sim F_x$ 。
${\hspace{20pt}}_\texttt{3.}\,$ 在数列后方删去 $x$ 个数，保证不会将数列删空。
${\hspace{20pt}}_\texttt{4.}\,$ 查询数列区间 $[x,y]$ 的最大值。
${\hspace{20pt}}_\texttt{5.}\,$ 查询数列区间 $[x,y]$ 的和。

$\hspace{15pt}$ 由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

$\hspace{15pt}$ 注意：输出的最大值应是取模前的最大值，例如对于数列 $\{998\,244\,354,998\,244\,352\}$ ，虽然 $998\,244\,352$ 在取模后是数列最大值，但是 $998\,244\,354$ 才是真正的数列最大值。

$\hspace{15pt}$ 在进行操作 $1,2,3$ 后，数列的下标可能会发生改变。例如在数列 $\{1,1,2\}$ 前方插入 $\{1,1\}$ 后，原本下标为 $1$ 的数字此时下标为 $3$ 。
$\hspace{15pt}$ 数列一开始为空，保证删除操作与查询操作保证数列内有足够的数。

输入描述:

第一行输入一个整数  代表操作次数。 
此后  行，每行先输入一个整数  代表操作类型，编号同题干。随后在同一行：
若 ，输入一个整数  代表插入的斐波那契数列的长度；
若 ，输入一个整数  代表删除的斐波那契数列的长度；
若 ，输入两个整数  代表查询的区间。

其中， 代表每次操作前数列的长度。

输出描述:

对于每一次第  类操作，新起一行。输出一个整数，表示查询结果。由于答案可能很大，请将答案对  取模后输出。

示例1

输入

复制

输出

复制

1
4

说明

在这个样例中，数列中的内容模拟如下：
尾插，；
删除，；
查询，，最大值结果为 ；
尾插，；
头插，；
查询，，和结果为 。

示例2

输入

复制

6
1 200000
2 100000
3 114514
4 1 114513
4 114514 114514
5 1 114514

输出

复制

10519474
970216009
55683470