eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Мама подарила мальчику Диме массив длины 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, по одному результату в строке.

Пример

Входные данные #1
3 3
1 2 3
? 1 3
= 2 3 2
? 1 3
Выходные данные #1
6
5
Автор Егор Куликов
Источник Зимняя Школа Харьков 2012