Вам даны два массива целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\). Вам нужно обработать \(q\) запросов двух типов:
- \(1\) \(l\) \(r\) \(x\): присвоить \(a_i := x\) для всех \(l \leq i \leq r\);
- \(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\)
Выходные данные
Для каждого запроса второго типа выведите ответ на задачу.
Примечание
В первом примере:
- Для первого запроса мы можем выбрать \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
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
|
5
30
|