E. Локация
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива целых чисел $$$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$$$

Входные данные

В первой строке находятся два целых числа $$$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$$$.

Выходные данные

Для каждого запроса второго типа выведите ответ на задачу.

Примеры
Входные данные
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
Входные данные
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
Примечание

В первом примере:

  • Для первого запроса мы можем выбрать $$$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$$$.