Курияма Мираи убила много чудовищ и получила в награду много (а именно n) камней. Все камни Курияма Мираи пронумерованы от 1 до n. Цена i-го камня равняется vi. Курияма Мираи хочет узнать некоторую информацию о своих камнях, с этой целью она задает вам вопросы. Каждый вопрос имеет один из следующих видов:
Вам нужно ответить правильно на ее вопросы, или Курияма Мираи скажет «fuyukai desu» (яп. неприятно) и расстроится.
В первой строке записано целое число n (1 ≤ n ≤ 105). Во второй строке записано n целых чисел: v1, v2, ..., vn (1 ≤ vi ≤ 109) – цены камней.
В третьей строке записано целое число m (1 ≤ m ≤ 105) — количество вопросов Курияма Мираи. Затем следует m строк, в каждой строке записано три целых числа: type, l и r (1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2), описывающих текущий вопрос. Если type равняется 1, то вам нужно вывести ответ на вопрос первого типа, в противном случае надо вывести ответ на вопрос второго типа.
Выведите m строк. В каждой строке должно быть записано целое число — ответ на вопрос Курияма Мираи. Выводите ответы на вопросы в порядке их следования во входных данных.
Пожалуйста, обратите внимание, что для хранения ответов на вопросы может быть не достаточно 32-битных целых чисел.
6 6 4 2 7 2 7 3 2 3 6 1 3 4 1 1 6
24 9 28
4 5 5 2 3 10 1 2 4 2 1 4 1 1 1 2 1 4 2 1 2 1 1 1 1 3 3 1 1 3 1 4 4 1 2 2
10 15 5 15 5 5 2 12 3 5
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач