Загадковий пристрій
Да, це сталось! Перший контеакт! Прибульці прибудуть на Землю у 2010! І вони пообіцяли привезти з собою загадковий пристрій, який неможливо зібрати використовуючи існуючі земні технології. Більша частина вчених світу думає саме так! Усі газети уже опублікували на перших сторінках статті про це.
На вхід пристрою подається послідовність {a_i}. Потім над нею виконуються наступні дві операції:
Виберемо інтервал [l; r] і виконаємо a_i ← a_i^2 mod 2010 для усіх таких i, що l ≤ i ≤ r.
Виберемо інтервал [l; r] і виведемо суму усіх a_i таких що l ≤ i ≤ r. Відмітимо, що сума не обчислюється по модулю 2010.
Дивно, що пристрій здатний виконати до 50 000 операцій вказаного виду над послідовністью з 50 000 чисел за 3 секунди. Ніхто до цього не міг такого зробити!
Проте Роман не вірить прибульцям і вважає що це усього лише чийсь великий обман з метою виграти мільйон доларів на біржі. Він хоче довести це. Він найняв Вас промоделювати роботу пристрою.
За заданою послідовністю a_i та набором операцій напишіть програму, яка промоделює роботу загадкового пристрою прибульців.
Вхідні дані
Перший рядок містить довжину послідовності n (1 ≤ n ≤ 50 000). Другий рядок містить n чисел a_i (0 ≤ a_i ≤ 2009), які задають початкову послідовність. Третій рядок містить кількість операцій m (1 ≤ m ≤ 50 000). Кожен з наступних m рядків описує операцію. j-та операція описується її типом k_j ('1' - піднесення до квадрату, '2' - обчислення суми), за яким йде два цілих числа l_j та r_j (1 ≤ l_j ≤ r_j ≤ n).
Вихідні дані
Для кожної операції другого типу у окремому рядку потрібно вивести відповідь.