描述

人生赢家有n个妹子。第i个妹子每隔a_i天去看望他一次。这个数可以为0,说明这个妹子一刻不停地陪在他身边。所有的a_i初始为0。
但是人生赢家的大脑似乎不太够用。共有q个事件会发生,每个是下列情况的一种:
1 l r x表示,令编号在区间[l,r]的妹子,每个妹子的a_i都增加x。
2 l r表示,此时人生赢家需要知道一个数,即编号在区间[l,r]的所有妹子的a_i的最大公约数。(至于他的目的他才不会告诉你呢~)
注意,gcd⁡(0,x)=x,其中x为任意自然数。
//本来还有一个操作,就是把某区间的a_i全部修改为某个数,但是为了迎合欢乐赛性质就不加了!

输入格式

第一行为两个整数n q。
接下来q行,每行符合题目描述中的格式。

输出格式

对于每个2操作,输出一行,即答案。

样例输入

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

样例输出

5
1
3
1

数据范围与约定

0≤n,q≤1,000,000,1≤l≤r≤n,1≤x≤1,000。

样例解释

在最初的几次1操作之后,a变为了{0,5,1,4,2,3}。