Курияма Мираи убила много чудовищ и получила в награду много (а именно n) камней. Все камни Курияма Мираи пронумерованы от 1 до n. Цена i-го камня равняется vi. Курияма Мираи хочет узнать некоторую информацию о своих камнях, с этой целью она задает вам вопросы. Каждый вопрос имеет один из следующих видов:
- Она называет вам два числа, l и r (1 ≤ l ≤ r ≤ n), а вы должны сказать ей, чему равна сумма
. - Пусть ui равняется цене i-го по дешевизне камня (цена, которая будет на i-ом месте, если расположить все цены камней в порядке неубывания). На этот раз она называет вам два числа, l и r (1 ≤ l ≤ r ≤ n), а вы должны сказать ей, чему равна сумма
.
Вам нужно ответить правильно на ее вопросы, или Курияма Мираи скажет «fuyukai desu» (яп. неприятно) и расстроится.
Выходные данные
Выведите m строк. В каждой строке должно быть записано целое число — ответ на вопрос Курияма Мираи. Выводите ответы на вопросы в порядке их следования во входных данных.
Примечание
Пожалуйста, обратите внимание, что для хранения ответов на вопросы может быть не достаточно 32-битных целых чисел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6
|
24
9
28
|
|
2
|
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
|