Загадочная надпись
Мистер Шерлок Холмс сильно скучает. Уже несколько месяцев ему не попадалась ни одно интересное дело, поэтому он играет в шахматы с Ватсоном. Но вот Холмс получает письмо от инспектора Грегсона, в котором говорится о загадочной смерти американца, тело которого нашли в заброшенном доме на Брикстон - роуд. Самое интересное заключалось в том, что на стене помещения жертвы было написано загадочную последовательность чисел.
Шерлок Холмс, как опытный детектив, понял, что эта последовательность является зашифрованным ключом. Доктор Ватсон предложил каждый элемент последовательности подносить к квадрату и потом считать сумму элементов на части последовательности. Шерлок Холмсу понравилась эта идея. Чтобы не потерять предыдущего результата, детективы решили после каждого возведения в квадрат, образованную последовательность переписывать на новый лист. Поскольку последовательность может быть очень большой, то они просят вашей помощи.
Операции возведения в квадрат и суммирования, брать по модулю 2014.
Входные данные
Первая строка содержит два числа n (1 ≤ n ≤ 100000) и m (1 ≤ m ≤ 100000), где n - количество чисел в последовательности, m - количество запросов.
Во второй строке задано n натуральных чисел - сама последовательность.
В последующих m строках заданы запросы двух типов:
1 x l r - в последовательности с номером x посчитать сумму на промежутке [l, r];
2 x - из последовательности x создать новую последовательность, каждый элемент которой возвести в квадрат.
Все номера запросов и позиции в последовательности начинаются с единицы. Гарантируется, что запросов к несуществующим версиям не будет. При обработке запроса второго типа, создается новая версия, которая получает номер j+1, где j - номер последней добавленной последовательности, сначала j = 0.
Выходные данные
Для каждого запроса суммы в отдельной строке нужно вывести ответ.