Wstęp do programowania w C++

Napisz program, który obsłuży operacje na tablicy liczb całkowitych. Program powinien umożliwiać dodawanie wartości na przedziale oraz obliczanie sumy elementów z dowolnego przedziału.

Input

W pierwszym wierszu znajduje się jedna liczba całkowita q (1 ≤ q ≤ 100 000) – liczba operacji.

W kolejnych q wierszach znajdują się operacje w jednym z dwóch formatów:

• 1 a b x – dodaj wartość x do wszystkich elementów w przedziale [a, b]
• 0 a b – wypisz sumę wszystkich elementów w przedziale [a, b]

Wszystkie indeksy a, b spełniają warunek 0 ≤ a ≤ b ≤ 1 000 000.

Output

Dla każdego zapytania typu 0 a b wypisz jedną liczbę w osobnej linii – sumę wartości z przedziału [a, b].

Example

Input:
4
1 0 2 3
0 0 2
1 1 3 2
0 0 3
Output:
9
15