Background

他依然记得华尔街的雪，想念阿坝州的风吟鸟唱，多年以后他才发现，华尔街本没有雪，冷的是人心。
愿你能够历尽山河，依然觉得人间值得。
来看一个有关的例子。

Description

斐波那契序列\(f_n\)满足\(f_0=f_1=1,f_{n+2}=f_n+f_{n+1},n\)为自然数。
现在有\(n\)个可重集合排成一列，编号分别为1~n，每个集合初始包含一个数\(f_1\)。
请支持如下四种操作：
1. 在第l~r号集合中各加入一个斐波那契数\(f_k\)。
2. 第l~r号集合中所有的斐波那契数\(f_x\)变为\(f_{x+k}\)。
3. 第l~r号集合中所有的斐波那契数变为\(f_k\)。
4. 查询l~r号集合中所有斐波那契数的和除以\(6324\)所得余数。
请注意，l~r号表示编号在区间\([l,r]\)的那些集合。

Format

Input

每个测试点仅包含一组输入数据。
第一行两个数\(n,m(n<=200000,m<=200000)\)，表示集合列长度和操作总数。
接下来\(m\)行，同一行中出现的整数用空格分隔，每行为如下四种格式之一：
1 l r k，表示进行操作\(1,l,r,k\)意义同题干描述。
2 l r k，表示进行操作\(2,l,r,k\)意义同题干描述。
3 l r k，表示进行操作\(3,l,r,k\)意义同题干描述。
4 l r，表示进行操作\(4\)，你需要输出结果。
对于全部的\(l,r,k\),有\(1<=l<=r<=n,1<=k<=10^9\)。

Output

按照输入顺序，对于每个操作\(4\)，输出一行一个整数表示本次查询的结果。

Sample 1

Input

10 10
1 1 10 1
2 1 6 6
1 4 4 10
4 9 10
2 8 10 4
4 5 6
2 4 8 2
3 1 8 1
2 1 3 1
4 1 4

Output

4
84
15

Limitation

3s, 1GB for each test case.

Source

2019网宿杯XMU程序设计竞赛现场赛