sqrt декомпозиция

В холле 179 школы, есть информационный стенд размером H×W (H – высота, W – ширина). На этом стенде размещается информация о кружках, изменениях в расписании, победах в олимпиадах, а также другая важная информация.

Первого сентября стенд был пуст. Одно за другим на нем начали появляться объявления, которые потом не снимались.

Каждое объявление представляет собой полоску бумаги единичной высоты. I-ое объявление представляет собой прямоугольник размером 1×W_i.

Когда кто-либо вешает объявление на стенд, то он старается повесить объявление как можно выше. Среди возможных верхних мест всегда выбирается самое левое. Если подходящего места для объявления не нашлось, то объявление не вешается на стенд. Ваша задача состоит в том, чтобы для каждого объявления определить, как высоко оно будет располагаться (в каком ряду).

Входные данные
Первая строка содержит три целых числа H, W и N (1≤H,W≤10⁹; 1≤N≤200000) — размеры стенда и количество объявлений. Каждая из следующих N строк содержит по одному целому числу W_i (1≤W_i≤10⁹) — ширину i-го объявления.

Выходные данные
Для каждого из объявлений (в порядке следования во входном файле) выведите номер ряда, в котором оно будет размещено. Ряды занумерованы от 1 до H сверху вниз. Если объявление разместить нельзя — выведите «–1».

Коренной житель Снежинска Даня Багров уже подрос, и пришло время найти работу. Конечно же, Даня захотел устроиться на завод.
Так как большинство заводов расположены в Челябинске (там их более 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).
Выходные данные
Для каждого запроса второго типа выведите ответ на задачу. Гарантируется, что хотя бы один такой запрос будет.
 

Примеры

№	Входные данные	Выходные данные
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

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

№	Входные данные	Выходные данные
1	7 abcdbcc	3
2	4 bbcb	2