Разреженные таблицы (sparse table)

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

Утром Колобок решил проанализировать свой сон. Он догадался, что в каждой клетке он был максимум один раз, но никак не может вспомнить, сколько клеток он посетил. Колобок просит вас написать программу, которая посчитает количество посещённых им клеток.




Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.
 

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.
 

Недавно вышла новая игра Counter-Strike 2. В 5-м классе учится N человек, и все они хотят поиграть в эту игру. На уроке физкультуры всех учеников построили в шеренгу. У физрука Олега Евгеньевича сегодня смешанное настроение: он решил разрешить ученикам поиграть в CS2 вместо физических занятий, но играть они будут только по определенным правилам. 

Олег Евгеньевич будет разрешать играть всем ученикам, номер в шеренге которых лежит в отрезке \([L;R]\). Олег Евгеньевич узнал, что родители детей разрешают играть им в компьютер только ti минут. Но ученики очень любят компьютерные игры, поэтому каждый будет играть ровно ti минут, при этом играть никто не отказывается. 

Игра происходит следующим образом: выбирается время матча такое, что каждый ученик должен сыграть строго целое число матчей, при этом количество сыгранных матчей у каждого ученика может различаться и время матча должно быть максимально возможным. 

Например, играют 2 игрока. Если у играющего 1 время \(t_1 = 12\), а у играющего 2 время \(t_2 = 8\), то максимально возможное время матча 4 минуты. 1 играющий сможет сыграть 3 матча по 4 минуты, а 2 – 2 матча по 4 минуты. 

Олег Евгеньевич в последнее время усердно занимается математикой, поэтому он решил M раз посчитать максимальное время Q для играющих от L до R. Вам следует проверить Олега Евгеньевича. Для этого следует вывести YES, если он прав, иначе – NO.

Входные данные
Первая строка содержит число N (\(1 <= N <= 10000\)) – количество ребят. Во второй строке записаны N чисел – ti (\(1 <= t_i <= 1000\)), время, которое дают родители i-ому ребенку на игру. В третьей строке записано число M (\(1 <= M <= 10^8\)), количество запросов. Далее, в M строках идут 3 числа L, R, Q (время, которое посчитал Олег Евгеньевич).

Выходные данные
Выведите для каждого запроса YES, если Олег Евгеньевич правильно посчитал, иначе – NO.

 

Примеры

№	Входные данные	Выходные данные
1	3 8 5 6 4 1 2 2 1 3 1 2 3 1 1 3 2	NO YES YES NO

Вам дан массив A [1…N]. Требуется выполнить M операций вычисления минимального элемента на отрезке с L по R.

Входные данные
Первая строка содержит число N (\(1 <= N <= 100000\)) – размер массива. Во второй строке записаны N чисел – элементы массива. Третья строка содержит число M (\(1 <= M <= 100000\)) – количество запросов минимума. Следующие M строк содержат пары чисел L и R (\(L <= R <= N\)), описывающие отрезки.

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

 

Примеры

№	Входные данные	Выходные данные
1	5 3 1 8 7 9 2 1 3 3 5	1 7