Коренной житель Снежинска Даня Багров уже подрос, и пришло время найти работу. Конечно же, Даня захотел устроиться на завод.
Так как большинство заводов расположены в Челябинске (там их более 60), Снежинску достался всего один, и, соответственно, спрос на такое желаемое место работы очень высок в этом городе, поэтому при устройстве на завод в Снежинске все сотрудники в обязательном порядке должны решить задачу по программированию.
Даня прогуливал в детстве информатику, поэтому с программированием у него всё плохо. Помогите Дане решить задачку, чтобы он смог без проблем устроиться на завод и жить в достатке.
Дано два массива целых чисел a
1,a
2,...,a
n и b
1,b
2,...,b
n и q запросов двух типов:
• 1 l r x — нужно сделать a
i = x для всех l <= i <= r.
• 2 l r — нужно найти минимальное значение
\( {lcm (a_i,b_i)\over gcd(a_i,b_i)}\) по всем l <= i <= r.
Входные данные
В первой строке находятся два целых числа n и q (1 <= n,q <= 5 · 10
4) — количество чисел в массивах a и b и количество запросов.
Во второй строке находятся n целых чисел a
1,a
2,...,a
n (1 <= a
i <= 5 · 10
4).
В третьей строке находятся n целых чисел b
1,b
2,...,b
n (1 <= b
i <=5 · 10
4).
Далее следует q строк, j-я из которых начинается с целого числа t (1 <= t <= 2) и означает, что j-й запрос относится к типу t.
Если t =1, то остальная часть строки содержит целые числа l, r и x (1 <= l <= r <= n, 1 <= x <= 5·10
4). Если t =2, то остальная часть строки содержит целые числа l и r (1 <= l <= r <= n).
Выходные данные
Для каждого запроса второго типа выведите ответ на задачу. Гарантируется, что хотя бы один такой запрос будет.
Примеры
| № |
Входные данные |
Выходные данные |
| 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 |