Загадковий пристрій#3318

Загадковий пристрій

1 секунда

256 мегабайтів

Складна

Так, це сталось! Перший контакт! Прибульці прибудуть на Землю у $2010$ ! І вони пообіцяли привезти з собою загадковий пристрій, який неможливо зібрати використовуючи існуючі земні технології. Більша частина вчених світу думає саме так! Усі газети уже опублікували на перших сторінках статті про це.

На вхід пристрою подається послідовність ${a_{i}}$ \{a_i\}. Потім над нею виконуються наступні дві операції:

Виберемо інтервал $[l; r]$ [l; r] і виконаємо $a_{i} \leftarrow a_{i}^{2} mod 2010$ a_i \leftarrow a_i^2 \bmod 2010 для усіх таких $i$ , що $l \leq i \leq r$ l \leq i \leq r.
Виберемо інтервал $[l; r]$ [l; r] і виведемо суму усіх $a_{i}$ a_i таких що $l \leq i \leq r$ l \leq i \leq r. Відмітимо, що сума не обчислюється по модулю $2010$ .

Дивно, що пристрій здатний виконати до $50000$ операцій вказаного виду над послідовністю з $50000$ чисел за $3$ секунди. Ніхто до цього не міг такого зробити!

Проте Роман не вірить прибульцям і вважає що це усього лише чийсь великий обман з метою виграти мільйон доларів на біржі. Він хоче довести це. Він найняв Вас промоделювати роботу пристрою.

За заданою послідовністю $a_{i}$ a_i та набором операцій напишіть програму, яка промоделює роботу загадкового пристрою прибульців.

Вхідні дані

Перший рядок містить довжину послідовності $n$ ( $1 \leq n \leq 50000$ 1 \leq n \leq 50000). Другий рядок містить $n$ чисел $a_{i}$ a_i ( $0 \leq a_{i} \leq 2009$ 0 \leq a_i \leq 2009), які задають початкову послідовність. Третій рядок містить кількість операцій $m$ ( $1 \leq m \leq 50000$ 1 \leq m \leq 50000). Кожен з наступних $m$ рядків описує операцію. $j$ -та операція описується її типом $k_{j}$ k_j ('1' - піднесення до квадрату, '2' - обчислення суми), за яким йде два цілих числа $l_{j}$ l_j та $r_{j}$ r_j ( $1 \leq l_{j} \leq r_{j} \leq n$ 1 \leq l_j \leq r_j \leq n).

Вихідні дані

Для кожної операції другого типу у окремому рядку потрібно вивести відповідь.

Приклади

Приклад 1