CF2257F1.Beaver's Jumping Track (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, the constraint on $x$ and time limit are lower. You can hack only if you solved all versions of this problem.

The Beaver is training to jump long distances. The Beaver can already jump $x$ meters. However, just jumping as far as possible is easy and boring. Therefore, the Beaver has created an unusual training track for jumping.

The track consists of $n$ platforms; each platform consists of $d_i$ meter cells. If the Beaver stands on platform number $i$, jumps, and lands back on the same platform, this results in $s_i$ penalty points being awarded; otherwise, no penalty points are given. The Beaver can jump forward any integer number of cells less than or equal to $x$. Note that the Beaver can skip one or more platforms in a single jump without landing on them at all.

The Beaver has unlimited computational power in its mind and always jumps in such a way as to minimize the total penalty for passing the track. Moreover, the track is not constant, and sometimes the lengths and penalties of some platforms change. Learn to calculate what penalty the Beaver will get if it starts standing on the first cell of platform number $l$ and finishes standing on the last cell of platform number $r$.

这是该问题的简单版本。两个版本的区别在于，本版本中对 $x$ 的限制以及时间限制更低。仅当您解决了该问题的所有版本后，才可进行 Hack。

海狸正在训练长距离跳跃。海狸当前已能跳跃 $x$ 米。然而，单纯地尽可能跳得更远是简单且枯燥的。因此，海狸设计了一条独特的跳跃训练轨道。

该轨道由 $n$ 个平台组成；每个平台由 $d_i$ 米长的格子构成。若海狸站在编号为 $i$ 的平台上起跳，并最终落回同一平台，则将被罚 $s_i$ 分；否则不产生罚分。海狸每次跳跃可向前跳跃任意不超过 $x$ 的整数个格子。注意：海狸在一次跳跃中可以跳过一个或多个平台，且完全不落在这些被跳过的平台上。

海狸拥有无限的脑内计算能力，总能以最小化通过整条轨道所需总罚分的方式进行跳跃。此外，轨道并非固定不变，有时某些平台的长度和罚分会发生变化。请编写程序，计算当海狸从编号为 $l$ 的平台的第一个格子出发，并最终落在编号为 $r$ 的平台的最后一个格子时，所获得的罚分。

The first line contains three integers $n$, $q$, $x$ — the number of sections of the track, the number of queries, and the maximum jump length, respectively ($1 \leq n \leq 10^6$; $1 \leq q \leq 10^4$; $1 \leq x \leq 5$).

The second line contains $n$ integers $d_i$ — the lengths of the platforms ($1 \leq d_i \leq 10^7$).

The third line contains $n$ integers $s_i$ — the penalties ($1 \leq s_i \leq 10^5$).

The following $q$ lines describe the queries in one of the following formats:

1. "1 $i$ $v$" — set the length of the $i$-th platform to $v$ ($1 \leq i \leq n$; $1 \leq v \leq 10^7$);
2. "2 $i$ $y$" — set the penalty on the $i$-th platform to $y$ ($1 \leq i \leq n$; $1 \leq y \leq 10^5$);
3. "? $l$ $r$" — calculate the minimum penalty for passing the track consisting of platforms from $l$ to $r$ ($1 \leq l \leq r \leq n$).

第一行包含三个整数 $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$）。

For each query of the third type, output a single number on a separate line — the minimum penalty.

对于每个第三种类型的查询，在单独一行输出一个数字——最小罚值。

During the first query, the lengths of the course sections are $[4, 2, 5]$ with costs $[4, 2, 7]$; the optimal route is

1 \\rightarrow 4 \\rightarrow 6 \\rightarrow 8 \\rightarrow 11$$ In this case, the penalty is $4 + 0 + 0 + 7 = 11$. Before the second query, the penalty of the second course increased, but we never get it; thus, the answer to this query is also $11$. Before the third query, we have the lengths of the courses $[2, 2, 5]$; then the route $$1 \\rightarrow 4 \\rightarrow 6 \\rightarrow 9$$ gives a penalty of 7, as the only penalizing jump is within one platform: $6 \rightarrow 9$. 第一次查询时，课程段的长度为 $[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$。