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$$$.

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$ .

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$ .