给定两个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$b_1, b_2, \ldots, b_n$$$。您需要处理以下两种类型的 $$$q$$$ 查询:
- $$$1$$$ $$$l$$$ $$$r$$$ $$$x$$$:为所有 $$$l \leq i \leq r$$$ 分配 $$$a_i := x$$$;
- $$$2$$$ $$$l$$$ $$$r$$$: 在所有$$$l \leq i \leq r$$$中找到以下表达式的最小值:$$$$$$\frac{\operatorname{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}.$$$$$$
在此问题中,$$$\gcd(x, y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最大公约数,$$$\operatorname{lcm}(x, y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最小公倍数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^4$$$) — 数组 $$$a$$$ 和 $$$b$$$ 中的数字数量以及查询数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^4$$$) — 数组 $$$a$$$ 的元素。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^4$$$) — 数组 $$$b$$$ 的元素。
然后是 $$$q$$$ 行,其中 $$$j$$$-th 以整数 $$$t_j$$$ ($$$1 \leq t_j \leq 2$$$) 开头,表示第 $$$j$$$ 查询的类型为 $$$t_j$$$。
如果 $$$t_j = 1$$$,则后跟三个整数 $$$l_j$$$、$$$r_j$$$ 和 $$$x_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$、$$$1 \leq x_j \leq 5 \cdot 10^4$$$)。
如果 $$$t_j = 2$$$,则后面跟着两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$)。
保证至少有一个 $$$2$$$ 类型的查询。
输出
对于第二类的每个查询,输出表达式的最小值。
示例
输入 #1
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
1 2 12 2 10 5 2
输入 #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
输出 #2
5 30
注意
在第一个示例中:
- 对于第一个查询,我们可以选择 $$$i = 4$$$。所以值为 $$$\frac{\operatorname{lcm}(4, 4)}{\gcd(4, 4)} = \frac{4}{4} = 1$$$。
- 第二次查询后,数组 $$$a = [6, 10, 15, 4, 9, 25, 9, 9, 9, 9]$$$。
- 对于第三个查询,我们可以选择 $$$i = 9$$$。所以值为 $$$\frac{\operatorname{lcm}(9, 18)}{\gcd(9, 18)} = \frac{18}{9} = 2$$$。
第二个:
- 对于第一个查询,我们可以选择 $$$i = 4$$$。所以值为 $$$\frac{\operatorname{lcm}(1, 5)}{\gcd(1, 5)} = \frac{5}{1} = 5$$$。
- 第二次查询后,数组 $$$a = [10, 18, 18, 5]$$$。
- 第三次查询后,数组 $$$a = [10, 10, 18, 5]$$$。
- 对于第四个查询,我们可以选择 $$$i = 2$$$。所以值为 $$$\frac{\operatorname{lcm}(10, 12)}{\gcd(10, 12)} = \frac{60}{2} = 30$$$。