You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

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

## Input Format
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$$$.

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

## Examples
```input
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
```
```output
1
2
12
2
10
5
2
```
-----
```input
4 4
10 2 12 5
1 12 16 1
2 2 4
1 2 3 18
1 2 2 10
2 2 3
```
```output
5
30
```

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

Now solve the problem and return the code.