小L的斐波那契数列游戏

【题目描述】

斐波那契数列是这样的一个数列

Fib[1] = 1

Fib[2] = 1

从Fib[3]开始满足Fib[n] = Fib[n-1]+Fib[n-2]

小L忽然对斐波那契数列着迷了呢。最开始小L有个长度为N，值全部为0的数列。之后小L可能会让数列下标[l, r]区间内的数，分别加上Fib[1], Fib[2], Fib[3]...Fib[1+r-l]。她还会时不时地查看数列中第p个数是多少。但是小L每次只有1s的时间玩这个好玩的游戏，你能帮帮她快速地完成这个游戏吗？

【输入格式】

第一行两个整数n. m，表示数列长度为n，小L会进行m个操作

下面m行，每行有一个操作。如果第一个数为0，后面跟一个数p，表示查询数列中第p个的值。如果第一个数为1，后面跟两个数l ,r。表示数列下标[l, r]范围内的数加上题面所述的斐波那契数列。

【输出格式】

对于每个询问操作输出其正确结果。由于这个结果可能非常大，只需输出其对 998244353 取模的结果。

【样例输入】

5 8
1 1 3
1 2 5
0 3
0 5
0 1
1 1 5
0 4
0 5  

【样例输出】

3
3
1
5
8

【提示】

对于样例的解释:

原始序列

0 0 0 0 0

修改操作[1,3]后

1 1 2 0 0

修改操作[2,5]后

1 2 3 2 3

查询3

输出3

查询5

输出3

查询1

输出1

修改操作[1,5]后

2 3 5 5 8

查询4

输出5

查询5

输出8

【数据范围】

n <= 10000

m <= 100000

数据随机生成，查询与修改操作比例约为1:1

输入文件共约11mb

泥萌意识到小L是谁了吗23333

【来源】

sxysxy