F1. Бобр на тренировке (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии ограничение на $$$x$$$ и ограничение по времени ниже. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Бобр тренируется прыгать в длину. Бобр уже умеет прыгать на $$$x$$$ метров. Однако просто прыгать как можно дальше — легко и скучно. Поэтому Бобр сделал себе необычную трассу для тренировки прыжков.

Трасса состоит из $$$n$$$ платформ, каждая платформа состоит из $$$d_i$$$ метровых ячеек. Штраф $$$s_i$$$ начисляется, если Бобр стоял на платформе номер $$$i$$$, прыгнул и приземлился снова на ту же платформу; в противном случае никакого штрафа не начисляется. Бобр может прыгнуть на любое целое количество ячеек вперёд, меньшее либо равное $$$x$$$. Обратите внимание, что Бобр может перепрыгнуть одну или несколько платформ одним прыжком, не наступая на них совсем.

Бобр обладает неограниченными вычислительными мощностями в своём разуме и всегда прыгает так, чтобы минимизировать суммарный штраф за прохождение трассы. Причём трасса непостоянна, и иногда длины и штрафы некоторых платформ меняются. Научитесь считать, какой штраф получит Бобр, если начнёт, стоя на первой ячейке платформы номер $$$l$$$, и закончит, стоя на последней ячейке платформы номер $$$r$$$.

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

Первая строка содержит три целых числа $$$n$$$, $$$q$$$, $$$x$$$ — количество участков трассы, количество запросов и максимальную длину прыжка соответственно ($$$1 \leq n \leq 10^6$$$; $$$1 \leq q \leq 10^4$$$; $$$1 \leq x \leq 5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$d_i$$$ — длины платформ ($$$1 \leq d_i \leq 10^7$$$).

Третья строка содержит $$$n$$$ целых чисел $$$s_i$$$ — штрафы ($$$1 \leq s_i \leq 10^5$$$).

В следующих $$$q$$$ строках описаны запросы в одном из следующих форматов:

  1. «1 $$$i$$$ $$$v$$$» — установить длину $$$i$$$-й платформы равной $$$v$$$ ($$$1 \leq i \leq n$$$; $$$1 \leq v \leq 10^7$$$);
  2. «2 $$$i$$$ $$$y$$$» — установить штраф на $$$i$$$-й платформе равным $$$y$$$ ($$$1 \leq i \leq n$$$; $$$1 \leq y \leq 10^5$$$);
  3. «? $$$l$$$ $$$r$$$» — посчитать минимальный штраф при прохождении трассы, состоящей из платформ от $$$l$$$ до $$$r$$$ ($$$1 \leq l \leq r \leq n$$$).
Выходные данные

Для каждого запроса третьего типа в отдельной строке выведите единственное число — минимальный штраф.

Пример
Входные данные
5 8 3
4 2 5 1 3
4 2 7 1 5
? 1 3
2 2 10
? 1 3
1 1 2
? 1 3
? 2 5
1 3 2
? 2 5
Выходные данные
11
11
7
7
0
Примечание

Во время первого запроса длины участков трассы это $$$[4, 2, 5]$$$, со стоимостями $$$[4, 2, 7]$$$; оптимальный маршрут имеет вид

$$$$$$1 \rightarrow 4 \rightarrow 6 \rightarrow 8 \rightarrow 11$$$$$$ В таком случае штраф равен $$$4 + 0 + 0 + 7 = 11$$$.

Перед вторым запросом штраф второй трассы увеличился, но при этом мы ни разу его не получали; значит, ответ на этот запрос тоже $$$11$$$.

Перед третьим запросом имеем длины трасс $$$[2, 2, 5]$$$; тогда маршрут $$$$$$1 \rightarrow 4 \rightarrow 6 \rightarrow 9$$$$$$ даёт штраф 7, так как единственный штрафной прыжок внутри одной платформы: $$$6 \rightarrow 9$$$.