Дима и массив 1

Мама подарила мальчику Диме массив длины $n$. Массив этот не простой, а особенный. Дима может выбрать три числа – $i,j$ и $d(1\le i\le j\le n,-1000\le d\le 1000)$, и все элементы с индексами от $i$ до $j$ магически становятся равными $d$. Дима играет со своим массивом, а мама время от времени задает ему вопросы – какова сумма всех чисел в массиве с индексами от $f$ до $t$? Дима легко справился с этими вопросами, сможете ли Вы?

Входные данные

В первой строке находятся два целых числа $n$ и $q(1\le n\le 5\cdot 10^5,1\le q\le 10^5)$ — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано $n$ чисел $a_1,a_2,...,a_n(-1000\le a_i\le 1000)$ — начальное состояние массива. В следующих $q$ строках заданы операции и запросы. Первый символ в строке может быть $=$ или $?$. Если строка начинается с $=$, то это операция присваивания. Далее следуют $i,j$ и $d$, ограничения на которые заданы выше. Если строка начинается с $?$, то это запрос. Далее следуют числа $f$ и $t(1\le f,t\le n)$.

Выходные данные

Для каждого запроса выведите сумму чисел в массиве с индексами от $f$ до $t$, по одному результату в строке.

Примеры