Задача: Работа в Снежинске

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

Примеры

Ваш ответ: