eolymp
Competitions

Пятёрка за неделю 23 (2013-2014)

Загадочная надпись

Мистер Шерлок Холмс сильно скучает. Уже несколько месяцев ему не попадалась ни одно интересное дело, поэтому он играет в шахматы с Ватсоном. Но вот Холмс получает письмо от инспектора Грегсона, в котором говорится о загадочной смерти американца, тело которого нашли в заброшенном доме на Брикстон - роуд. Самое интересное заключалось в том, что на стене помещения жертвы было написано загадочную последовательность чисел.

Шерлок Холмс, как опытный детектив, понял, что эта последовательность является зашифрованным ключом. Доктор Ватсон предложил каждый элемент последовательности подносить к квадрату и потом считать сумму элементов на части последовательности. Шерлок Холмсу понравилась эта идея. Чтобы не потерять предыдущего результата, детективы решили после каждого возведения в квадрат, образованную последовательность переписывать на новый лист. Поскольку последовательность может быть очень большой, то они просят вашей помощи.

Операции возведения в квадрат и суммирования, брать по модулю 2014.

Входные данные

Первая строка содержит два числа n (1n100000) и m (1m100000), где n - количество чисел в последовательности, m - количество запросов.

Во второй строке задано n натуральных чисел - сама последовательность.

В последующих m строках заданы запросы двух типов:

  • 1 x l r - в последовательности с номером x посчитать сумму на промежутке [l, r];
  • 2 x - из последовательности x создать новую последовательность, каждый элемент которой возвести в квадрат.

Все номера запросов и позиции в последовательности начинаются с единицы. Гарантируется, что запросов к несуществующим версиям не будет. При обработке запроса второго типа, создается новая версия, которая получает номер j+1, где j - номер последней добавленной последовательности, сначала j = 0.

Выходные данные

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
5 5
1 2 3 4 5
1 0 1 5
2 0
1 1 1 5
2 1
1 2 2 4

Output example #1
15
55
353
Author Александр Цицюра