DZY любит цвета, он обожает рисовать.
В один «цветастый» день DZY получил цветную ленточку, состоящую из n сегментов (пронумерованных от 1 до n слева направо). Цвет i-го сегмента ленточки изначально равняется i. Насыщенность цвета каждого сегмента ленточки изначально равна 0.
Как известно, DZY любит рисовать. Иногда, он берет кисть цвета x и проводит ей линию на ленточке. В таком случае закрашиваются некоторые последовательные сегменты. Представим, что текущий цвет сегмента i равняется y. Когда сегмент закрашивается кистью цвета x, его цвет становится равен x, а насыщенность цвета сегмента возрастает на |x - y|.
DZY хочет выполнить m операций, каждая операция может быть:
- Покрасить все сегменты с номерами от l до r (обе границы включительно) кистью цвета x.
- Посчитать сумму насыщенностей цветов сегментов с номерами от l до r (обе границы включительно).
Поможете DZY?
Выходные данные
Для каждой операции типа 2, выведите ответ в отдельной строке — сумму насыщенностей.
Примечание
В первом примере изначально цвет каждого сегмента равен [1, 2, 3], а насыщенность цвета каждого сегмента равна [0, 0, 0].
После первой операции цвета меняются на [4, 4, 3], насыщенности равняются [3, 2, 0].
После второй операции цвета меняются на [4, 5, 5], насыщенности равняются [3, 3, 2].
Таким образом, ответ на единственную операцию типа 2 равен 8.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 1 2 4
1 2 3 5
2 1 3
|
8
|
|
2
|
3 4
1 1 3 4
2 1 1
2 2 2
2 3 3
|
3
2
1
|
|
3
|
10 6
1 1 5 3
1 2 7 9
1 10 10 11
1 3 8 12
1 1 10 3
2 1 10
|
129
|