Мама подарила мальчику Диме массив длины $n$. Массив этот не простой, а особенный. Дима может выбрать три числа -- $i, j$ и $d\: (1 \le i \le j \le n, -1000 \le d \le 1000)$, и все элементы с индексами от $i$ до $j$ магически становятся равными $d$. Дима играет со своим массивом, а мама время от времени задает ему вопросы -- какова сумма всех чисел в массиве с индексами от $f$ до $t$? Дима легко справился с этими вопросами, сможете ли Вы? \InputFile В первой строке находятся два целых числа $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)$. \OutputFile Для каждого запроса выведите сумму чисел в массиве с индексами от $f$ до $t$, по одному результату в строке.