Задача 6D. Range Variation Query

Входной файл:rvq.in   Ограничение времени:2 сек
Выходной файл:rvq.out   Ограничение памяти:256 Мб

Условие

В начальный момент времени последовательность an задана следующей формулой: an = n2 mod 12345 + n3 mod 23456.

Требуется много раз отвечать на запросы следующего вида:

Формат входного файла

Первая строка входного файла содержит натуральное число k — количество запросов (1 ≤ k ≤ 100 000).

Следующие k строк содержат запросы, по одному на строке. Запрос номер i описывается двумя целыми числами xi, yi.

Если xi > 0, то требуется найти разность между максимальным и минимальным значениями среди элементов axi, …, ayi. При этом 1 ≤ xi ≤ yi ≤ 100 000.

Если xi < 0, то требуется присвоить элементу a|xi| значение yi.

В этом случае  − 100 000 ≤ xi ≤  − 1 и |yi| ≤ 100 000.

Формат выходного файла

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

Ограничения

Примеры тестов

Входной файл (rvq.in) Выходной файл (rvq.out)
1
7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3
34
68
250
234
1

0.162s 0.028s 15