Location
Contest: Codeforces Round 830 (Div. 2)
Difficulty rating: 2800
Tags: data structures, dp, math, number theory

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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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

Example 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

Example output:
1
2
12
2
10
5
2

Example 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

Example output:
5
30

Editorial:
Tasks of this kind, as a rule, are solved using data structures, and this one is no exception. Since the constraints in the problem are not large enough, it is logical to think in the direction of root optimizations.
Let's divide the array into blocks of length $$$k$$$, we will have about $$$\frac{n}{k}$$$ such blocks. For each block, we want to maintain a response, i.e. a minimum value of $$$\frac{lcm(a_i, b_i)}{gcd(a_i, b_i)}$$$.
Let's see what happens with the first type of operation. If the block partially intersects with the segment of the request, then it is possible to go through this block for $$$O(k)$$$ and recalculate the answer. There are no more than two such blocks, so in total we will spend $$$O(k)$$$ on this (we neglect the running time of $$$\gcd$$$). If the block lies entirely in the segment of the request (and there can be $$$\frac{n}{k}$$$ such blocks), then you need to somehow recalculate the response more quickly.
To do this, let's precalculate the following value for each block: $$$answer_x$$$ — what will be the answer in the block if we assign the value $$$x$$$ to all numbers. Let's learn how to calculate the answer for a fixed $$$x$$$ first. To do this, let's iterate over all divisors $$$d$$$ of the number $$$x$$$ — in fact, by enumeration of this divisor, we will try to fix $$$\gcd$$$. Then note that since we want the value to minimize the value, we need to find the minimum value of $$$b_i$$$ that is divisible by $$$d$$$. And then we make $$$answer_x = \min(\frac{b_i}{d})$$$ over all such $$$d$$$. Let's note that $$$\gcd(b_i, x)$$$ may not actually be equal to $$$d$$$, but we know for sure that $$$\gcd(b_i, x) \geq d$$$, and since we want to minimize the value , then we do not do worse.
Already now we can calculate the answer for $$$A \log A$$$ inside the block, where $$$A$$$ is the maximum value. But you can do even better!
Let's note that $$$answer_x = min(answer_{\frac{x}{p}} \cdot p)$$$ where $$$p$$$ is a prime divisor of $$$x$$$, and don't forget the case when $$$d = x$$$ . This follows from the fact that all divisors of the number $$$x$$$ are contained among the divisors of numbers of the form $$$\frac{x}{p}$$$.
Let's calculate the running time and find the optimal $$$k$$$. We need to find all its divisors for each number in order to quickly find out the minimum number that is divisible by the given one inside the block — we do this in $$$O(n \sqrt A)$$$. Inside each block, our precalculation now works for $$$O(A \log \log A)$$$, that is, in total for all blocks $$$O(\frac{n}{k} \cdot A \log \log A)$$$. We answer the request for $$$O(k \cdot \gcd + \frac{n}{k})$$$. Hence we get that it is advantageous to take $$$k$$$ approximately $$$\sqrt n$$$ (we have all quantities of the same order, so we use $$$n$$$).