Problem description

Jeśli dotarłeś do tego miejsca, oznacza to, że jesteś już całkiem wprawionym eksploratorem Pospolitych Lasów Przedziałowych, oczywiście następnym poziomem są Tropikalne Lasy Przedziałowe, a potem i same Egzotyczne Lasy Przedziałowe. Aktualnie wchodzisz, z każdym krokiem (zadaniem), coraz to głębiej w Tropikalny Las Przedziałowy. Twój strach rośnie. W każdej chwili może wyskoczyć i zaatakować Cię przerażające drzewo przedziałowe. I tak też się stało, wyskakuje na Ciebie

Wyjątkowo groźne drzewo przedział-przedział, które wymaga od Ciebie wykonywania (w czasie prawie ujemnym) Q operacji dwóch typów:

• update A_i B_i C_i – ustaw na przedziale od A_i do B_i wartość C_i,
• query A_i B_i – podaj sumę na przedziale od A_i do B_i.

Aby przeżyć spotkanie z tym drzewem musisz wykazać się wściekłością i szybko spełnić jego wymagania, w przeciwnym przypadku spotka Cię marny koniec: Sam wiesz kto zje Ci śniadanie.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, oznaczająca liczbę operacji do wykonania. W kolejnych Q wierszach znajdują się opisy operacji, zgodne z opisem powyżej.

Wyjście

Na wyjście należy wypisać jedną liczbę, dla każdej operacji typu query – odpowiedź na dane zapytanie.

Ograniczenia

1 ≤ Q ≤ 1 000 000, 1 ≤ A_i ≤ B_i ≤ 1 000 000, 0 ≤ C_i ≤ 10⁹.

Przykład

8
update 2 4 3
update 1 3 2
query 2 3
query 4 4
query 1 1
update 7 7 1
query 1 7
query 4 7

4
3
2
10
4