Range Variation Query
Range Variation Query
Последовательность a_n задается следующей формулой: a_n = n^2mod 12345 + n^3 mod 23456.
Требуется много раз отвечать на запросы следующего вида:
найти разность между максимальным и минимальным значением среди элементов a_i, a_{i+1}, ..., a_j;
присвоить элементу a_i значение j.
Входные данные
Первая строка содержит натуральное число k (k ≤ 100 000) - количество запросов. Следующие k строк содержат запросы, по одному в строке. Запрос номер i описывается двумя целыми числами x_i, y_i.
Если x_i > 0, то требуется найти разность между максимальным и минимальным значением среди элементов a_xi...a_yi. При этом 1 ≤ x_i ≤ y_i ≤ 100 000.
Если x_i < 0, то требуется присвоить элементу a_{-xi} значение y_i. При этом -100 000 ≤ x_i ≤ -1 и |y_i| ≤ 100 000.
Выходные данные
Для каждого запроса первого типа требуется вывести в отдельной строке разность между максимальным и минимальным значением на соответствующем отрезке.
Пример
7 1 3 2 4 -2 -100 1 5 8 9 -3 -101 2 3
34 68 250 234 1