Migrated from Lutece 3125 Powder Snow

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

Tag：分块

Wie geht es Ihnen? Ich singe immer noch.

为了缓解打完《WHITE ALBUM 2》后带来的胃痛，空気力学の詩只得狂刷题目以转移注意力，但现在他被如下所述的一道题难住了。

给出长为 $n$ 的序列 $\{a_n\},\{b_n\}$ ，同时有 $q$ 次操作需要处理，操作格式形如：

• 1 l r x：对于所有的 $i\in[l,r]$ ，将 $a_i$ 的值改为 $x$ 。

• 2 l r：求出 $\min_{l\le i\le r} \frac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}$ 的值，其中 $\operatorname{lcm}(x,y)$ 表示 $x,y$ 的最小公倍数， $\gcd(x,y)$ 表示 $x,y$ 的最大公约数。

请你帮助他解决这个问题，不然他只能继续被胃痛所折磨了。

Input

输入的第一行包括两个正整数 $n,q$ ，分别表示序列 $\{a_n\},\{b_n\}$ 的长度以及需要处理的操作数量。

第二行包括一个长为 $n$ 的序列 $\{a_n\}$ ，第三行包括一个长为 $n$ 的序列 $\{b_n\}$ 。

接下来的 $q$ 行每行一个操作，格式与意义如题面所述。

Output

对于每个第二种类型的操作，输出一行一个正整数表示答案。

Samples

10 10
6 10 15 4 9 25 2 3 5 30
1 2 3 4 6 9 12 15 18 30
2 1 10
1 7 10 9
2 5 10
1 1 6 14
2 4 7
2 3 9
1 2 9 30
2 1 4
2 3 7
2 5 10

1
2
12
2
10
5
2

4 4
10 2 12 5
1 12 16 1
2 2 4
1 2 3 18
1 2 2 10
2 2 3

5
30

Constraints

$1\le n,q,a_i,b_i\le 5\times 10^4$

对于所有操作，均有 $1\le l\le r\le n$ ，且第一类操作的$x$满足 $1\le x\le 5\times 10^4$

Resources

2024 UESTC ICPC Training for Data Structures