题目描述
有一个长度为 n 的序列 a1,a2,⋯,an,保证 ai 为奇数。
有两种操作:
- 给定 l,r,x,将 al,al+1,⋯,ar 加上偶数 x;
- 给定 l,r,求 al,al+1,⋯,ar 的乘积,答案对 220 取模;
输入格式
从标准输入读入数据。
第一行两个正整数 n,q 表示序列的长度和询问的个数. 保证 1≤n,q≤2×105。
第二行 n 个奇数 a1,a2,⋯,an. 保证 1≤ai<220。
接下来 q 行,每一行表示一个操作,格式为以下两种之一:
- 1 l r x:表示进行第一种操作. 保证 1≤l≤r≤n,0≤x<220。
- 2 l r:表示进行第二种操作. 保证 1≤l≤r≤n。
输出格式
输出到标准输出。
对于每一次 2 操作,输出一行一个整数表示答案。
样例
输入
10 10
969575 741825 24903 1047319 450475 256145 1045323 479255 810659 768323
1 5 6 3034
2 1 10
2 1 9
2 1 4
1 3 6 126904
2 5 5
2 9 9
1 7 7 853094
1 4 9 1025178
2 5 8
输出
1045541
1012343
558151
580413
810659
527353