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