CF1732E.Location

You are given two arrays of integers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$. You need to handle $q$ queries of the following two types:

• $1$ $l$ $r$ $x$: assign $a_i := x$ for all $l \leq i \leq r$;
• $2$ $l$ $r$: find the minimum value of the following expression among all $l \leq i \leq r$: $$\frac{\operatorname{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}.$$

In this problem $\gcd(x, y)$ denotes the greatest common divisor of $x$ and $y$, and $\operatorname{lcm}(x, y)$ denotes the least common multiple of $x$ and $y$.

给你两个整数数组 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$。你需要处理 $q$ 个如下两类查询：

• $1$ $l$ $r$ $x$：对所有满足 $l \leq i \leq r$ 的下标 $i$，令 $a_i := x$；
• $2$ $l$ $r$：在所有满足 $l \leq i \leq r$ 的下标 $i$ 中，求下列表达式的最小值：

  $$\frac{\operatorname{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}.$$

本题中，$\gcd(x, y)$ 表示 $x$ 与 $y$ 的最大公约数，$\operatorname{lcm}(x, y)$ 表示 $x$ 与 $y$ 的最小公倍数。

The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 5 \cdot 10^4$) — the number of numbers in the arrays $a$ and $b$ and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 5 \cdot 10^4$) — the elements of the array $a$.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 5 \cdot 10^4$) — the elements of the array $b$.

Then $q$ lines follow, $j$-th of which starts with an integer $t_j$ ($1 \leq t_j \leq 2$) and means that the $j$-th query has type $t_j$.

If $t_j = 1$, it is followed by three integers $l_j$, $r_j$, and $x_j$ ($1 \leq l_j \leq r_j \leq n$, $1 \leq x_j \leq 5 \cdot 10^4$).

If $t_j = 2$, it is followed by two integers $l_j$ and $r_j$ ($1 \leq l_j \leq r_j \leq n$).

It is guaranteed that there is at least one query of type $2$.

第一行包含两个整数 $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$ 行以一个整数 $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$ 的查询。

For each query of the second type, output the minimum value of the expression.

对于每个第二类查询，输出该表达式的最小值。

In the first example:

• For the first query we can choose $i = 4$. So the value is $\frac{\operatorname{lcm}(4, 4)}{\gcd(4, 4)} = \frac{4}{4} = 1$.
• After the second query the array $a = [6, 10, 15, 4, 9, 25, 9, 9, 9, 9]$.
• For the third query we can choose $i = 9$. So the value is $\frac{\operatorname{lcm}(9, 18)}{\gcd(9, 18)} = \frac{18}{9} = 2$.

In the second:

• For the first query we can choose $i = 4$. So the value is $\frac{\operatorname{lcm}(1, 5)}{\gcd(1, 5)} = \frac{5}{1} = 5$.
• After the second query the array $a = [10, 18, 18, 5]$.
• After the third query the array $a = [10, 10, 18, 5]$.
• For the fourth query we can choose $i = 2$. So the value is $\frac{\operatorname{lcm}(10, 12)}{\gcd(10, 12)} = \frac{60}{2} = 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$。