Загадковий напис
Містер Шерлок Холмс дуже нудьгує. Вже кілька місяців йому не траплялося жодної цікавої справи, тому він грає в шахи з Ватсоном. Але ось Холмс отримує листа від інспектора Грегсона, в якому йдеться про загадкову смерть американця, тіло якого знайшли в покинутому будинку на Брікстон-роуд. Найцікавіше полягало в тому, що на стіні приміщення жертви було написано загадкову послідовність чисел.
Шерлок Холмс, як досвідчений детектив, зрозумів, що ця послідовність є зашифрованим ключем. Доктор Ватсон запропонував кожен елемент послідовності підносити до квадрату і потім рахувати суму елементів на частині послідовності. Шерлоку Холмсу сподобалася ця ідея. Щоб не втратити попереднього результату, детективи вирішили після кожного піднесення до квадрату, утворену послідовність переписувати на новий лист. Оскільки послідовність може бути дуже великою, то вони просять вашої допомоги.
Операції піднесення до квадрату і сумування виконуються по модулю 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.
Вихідні дані
Для кожного запиту суми в окремому рядку потрібно вивести відповідь.