Задача №1696. Инопланетная машинка
Наконец-то это случилось! Пришельцы посетят Землю уже в 2010 году! Все газеты пишут о сенсационной находке. Пришельцы высадились в далёкой африканской пустыне и оставили загадочное устройство в знак подтверждения своего существования.
Это устройство принимает на вход последовательность целых чисел \(a_i\) , и после этого может производить следующие две операции с ней:
1) Взять интервал [\(l\);\(r\)] и выполнить присваивание \(a_i\) <- \(a_i\)2mod2010 для всех \(a_i\) таких, что \(l\) \(\le\) \(i\) \(\le\) \(r\).
2) Взять интервал [\(l\);\(r\)] и вывести сумму всех \(a_i\) таких, что \(l\) \(\le\) \(i\) \(\le\) \(r\). Обратите внимание, что сумма не берётся по модулю 2010.
Потрясающе, что это устройство может производить 200000 операций такого вида с последовательностью из 200000 чисел за 2 секунды! Никому раньше подобное не удавалось!
Но Рома не верит в пришельцев и считает, что это — очередная мистификация, сфабрикованная кем-то с целью выиграть ещё пару гигабаксов на бирже. Поэтому он нанял вас написать программу, симулирующую это устройство.
Напишите программу, которая по данной последовательности целых чисел ai и последовательности операций будет симулировать поведение этого странного «инопланетного» устройства.
В первой строке ввода содержится длина последовательности \(n\) (1 \(\le\) \(n\) \(\le\) 200000). Вторая строка содержит n целых чисел \(a_i\) (0 \(\le\) \(a_i\) \(\le\) 2009). В третьей строке дано число операций \(m\) (1 \(\le\) \(m\) \(\le\) 200000). Оставшаяся часть файла состоит из \(m\) строк, каждая из которых описывает одну операцию; \(j\)-я операция описывается её типом \(k_j\) («1» для возведения в квадрат по модулю, «2» для вычисления суммы), после которого через пробелы написаны \(l_j\) и \(r_j\) (1 \(\le\) \(l_j\) \(\le\) \(r_j\) \(\le\) \(n\)).
Для каждой операции второго типа выведите её результат на отдельной строке, в порядке выполнения операций.
3 17 239 999 4 2 1 3 1 2 3 2 2 3 2 1 2
1255 1882 858