Migrated from Lutece 2375 我，不是说了能力要平均值么 · 改

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

转生异世界时，栗原海里请求神赐予她平均值的能力，导演组故意找了一个不会计算平均数的神，神很自然地给出了最大值与最小值和的一半的结果——在数学上这显然是错误的，但是剧情就变得很有意思了。

形式化地，若有一由 $n$ 个数组成的有限数列 $\{x_n\}$，则这列数的平均值应为 $\bar x=\frac{1}{n}\sum_{i=1}^n x_i$。栗源海里显然知道平均数应该怎么计算，于是她在思考如果利用真正的平均值定义的话情况会是怎样的。

异世界共有 $n$ 个生物，每个生物都有一个能力值 $a_i$。神会选择一个区间 $[l,r]$，将编号在这个范围内的生物能力的平均值给栗原海里。但是根据辩证唯物主义，物质是运动的，在某个时刻，编号在某段区间 $[x,y]$ 内的生物能力值会集体变为各自能力值的五次方。

这样两种事件一共发生 $m$ 次，对于每个求平均值的事件，请把能力平均值对 $73156157$ 取模后的值告诉栗原海里。

Input

第一行两个正整数 $n,m$；

第二行 $n$ 个整数 $a_i$，表示每个生物的初始能力值；

接下来 $m$ 行，按时间顺序给出，每行表示一个事件：

• $\texttt{1 l r}$：表示编号在 $[l,r]$ 区间内的生物能力值都变为原来的五次方；
• $\texttt{2 x y}$：表示询问目前编号在 $[x,y]$ 区间的活着的生物能力的平均值，在模 $73156157$ 意义下输出。

Output

对于每次询问，输出一个整数，代表所求平均值对 $73156157$ 取模后的值。

对于一个表示成 $\frac{p}{q}$ 的有理数（其中 $p\in \mathbb{N},q\in \mathbb{N}_+$，且 $\gcd(p,q)=1$），请输出 $p\times q^{-1}$ 对 $73156157$ 取模后的值，其中 $q^{-1}$ 表示 $q$ 在模 $73156157$ 意义下的逆元。

Samples

6 3
1 1 4 5 1 4
2 2 6
1 3 5
2 1 3

3
342

9 14
7325 516 56940 120670 16272 15007 337527 333184 742294
2 5 5
2 6 6
2 2 7
1 1 8
2 4 9
2 6 6
2 5 6
1 5 6
1 3 8
2 4 7
2 6 7
1 1 4
2 5 9
2 1 6

16272
15007
24476541
20317610
15593759
28649378
38510325
52781047
42809369
31512621

Constraints

$1\le n,m\le 2\times 10^5,0\le a_i<73156157,1\le l\le r\le n,1\le x\le y\le n$

Note

对于第一个样例，第一次询问时所有生物的能力值为 $\{1,1,4,5,1,4\}$，编号在 $[2,6]$ 区间内的生物能力平均值为 $\frac{1+4+5+1+4}{5}=3$，取模后仍为 $3$。第二次询问时所有生物的能力值为 $\{1,1,4^5,5^5,1^5,4\}$，编号在 $[1,3]$ 区间内的生物能力平均值为 $\frac{1+1+4^5}{3}=342$，取模后仍为 $342$。

若 $\exists t\in[1,P),t\in \mathbb{N}_+$，满足 $at\equiv 1\pmod P$，则称 $t$ 为 $a$ 在模 $P$ 意义下的逆元。记作 $a^{-1}$。

逆元的求解并不是本题的考点，可以查阅资料自行学习。

Resources

2020 UESTC ICPC Training for Data Structures