У Ярослава есть n точек, лежащих на оси Ox. Координата первой точки — x1, второй — x2, ..., n-ой — xn. Сейчас Ярослав хочет выполнить m запросов, каждый из которых одного из двух следующих типов:
- Переместить pj-тую точку из позиции xpj в позицию xpj + dj. При этом гарантируется, что после выполнения запроса ни у каких двух точек координаты не совпадут.
- Посчитать сумму расстояний между всеми парами точек, которые лежат на отрезке [lj, rj] (lj ≤ rj). Другими словами, требуется посчитать сумму:
.
Помогите Ярославу.
Выходные данные
Для каждого запроса второго типа выведите ответ в отдельной строке. Ответы выводите в порядке следования запросов во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
36 50 28 -75 40 -60 -95 -48
20
2 -61 29
1 5 -53
1 1 429
1 5 130
2 -101 -71
2 -69 53
1 1 404
1 5 518
2 -101 53
2 50 872
1 1 -207
2 -99 -40
1 7 -389
1 6 -171
1 2 464
1 7 -707
1 1 -730
1 1 560
2 635 644
1 7 -677
|
176
20
406
1046
1638
156
0
|