斐波
题号：NC212280
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

假设 fib(n) 为斐波那契数列的第n项，其中fib(0)=0, fib(1)=1，且fib(n)=fib(n-1)+fib(n-2), (n>1)。

假设S是一个可重集合 ，f(S) 定义为



有一个数组a_1,a_2,...,a_n，牛妹会对数组进行q次操作，每次操作可能是以下两种操作中的一种：

1. 把a_p变为v；
2. 计算 。

对于每个操作2，输出答案模998244353。

输入描述:

第一行两个整数n, q。
第二行n个整数a_1,a_2,...,a_n 
接下来q行，每行代表一个操作：
如果是操作1，格式为1 p v ； 
如果是操作2，格式为2 l r

输出描述:

输出答案，模998244353。
示例1

输入

复制 
5 3
1 2 3 4 5
2 1 2
1 2 3
2 1 2

输出

复制 
8
19

说明

第一个询问:
f(\{1\}) = fib^2(0) + fib^2(1) = 1 
f(\{1,2\}) = fib^2(0) + fib^2(1) + fib^2(2) + fib^2(3) = 6 
f(\{2\}) = fib^2(0) + fib^2(2) = 1 
f({1})+f({1,2})+f({2}) = 8 
第二个操作把数列改变为 1 3 3 4 5
第三个询问:
f({1})+f({1,3})+f({3})=1+14+4=19
示例2

输入

复制 
10 10
883 219 454 809 569 200 178 387 304 716
2 4 10
1 4 368
2 4 8
2 1 8
1 5 764
2 2 4
2 5 7
1 2 174
1 5 115
2 3 8

输出

复制 
377148874
524944841
251771778
173440185
184756056
974115131

备注:

对于10%的数据，满足 
对于50%的数据，满足 
对于70%的数据，满足 
对于100%的数据，满足 ,
, 
。