Задача A. Сумма ≡

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

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

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

• A i x — присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 10⁹)
• Q l r — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

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

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

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

5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5

0
2
1
2
0
5

Задача B. Range Variation Query ≡

Условие

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

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

• Найти разность между максимальным и минимальным значениями среди элементов a_i, a_i + 1, …, a_j.
• Присвоить элементу a_i значение j.

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

Первая строка входного файла содержит натуральное число k — количество запросов (1 ≤ 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

Задача C. Сумма+присвоение на отрезке ≡

Условие

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

Первая строка входного файла содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы:

• A l r x

   — присвоить элементам массива с позициями от l до r значение x (1 ≤ l ≤ r ≤ N, 0 ≤ x ≤ 10⁹)

• Q l r

   — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ N)

Изначально массив заполнен нулями.

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

На каждый запрос вида

Q l r

Ограничения

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

5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5

3
2
3
4
2
7

Задача D. RMQ ≡

Условие

• «max l r». Найти максимум в массиве a от l-ой ячейки до r-ой включительно.
• «add l r v». Прибавить значение v к каждой ячейке a[] от l-ой до r-ой включительно.

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

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 10⁵) — длина массива и число запросов соответственно.

Вторая строка содержит n целых чисел a₁, …, a_n (|a_i| ≤ 10⁵), задающих соответствующие значения массива.

Следующие q строк содержат запросы.

В зависимости от типа запрос может иметь вид либо «max l r», либо «add l r v».

1 ≤ l ≤ r ≤ n, |v| ≤ 10⁵.

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

Для каждого запроса вида «max l r» требуется в отдельной строке выдать значение соответствующего максимума.

Ограничения

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

5 3
1 2 3 4 -5
max 1 3
add 1 2 5
max 1 3

3
7

Задача E. Выборы заведующего кафедрой ≡

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.

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

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

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

Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4