Description

Although the Human Village can be said to be the safest place for humans in all of Gensokyo, accidents may still happen when an incident occurs, so shelters need to be built.

The Human Village can be abstracted as a coordinate axis, on which there are $n$ points with houses built. The coordinates of these houses are $x_1, x_2, ..., x_n$, and in the $i$-th house there live $v_i$ residents.

Each time an incident occurs, a coordinate-contiguous segment of houses will be affected, and then it is necessary to build a shelter at some coordinate. The "inconvenience" of a shelter is the sum, over every resident in the affected houses, of their distance to the shelter.

(For example, suppose only house $i$ is affected. Then the "inconvenience" of building the shelter at $z$ is $v_i*|x_i-z|$.)

Of course, the Human Village in Gensokyo cannot stay unchanged, so both house positions and resident counts may change.

Specifically, you need to process $m$ queries or modifications. Each input is in one of the following formats:

• 1 l r: Query, when the houses whose coordinates lie in $[l, r]$ are affected by the incident, among all ways to build a shelter, what is the minimum possible "inconvenience".

• 2 a b c: Modify the $a$-th house: change its coordinate to $b$, and change the number of residents living in it to $c$.

Notes:

• In operation 1, the "affected by the incident" is only a hypothesis, so it does not affect later queries.

• In operation 2, the changed object is the $a$-th house, not the house whose coordinate is $a$.

Input Format

The first line contains two integers, $n, m$.

The second line contains $n$ integers, $x_i$.

The third line contains $n$ integers, $v_i$.

The next $m$ lines each describe one operation.

Output Format

For each 1 l r operation, output the minimum "inconvenience" for building the shelter.

10 10
-2 -3 -7 2 -6 7 -3 -5 4 -7 
0 2 2 0 4 6 2 4 3 3 
1 4 7
1 -5 7
1 -1 8
2 8 9 2
2 7 -3 5
2 7 4 3
2 2 -1 7
1 -9 -7
2 2 3 1
1 -1 0

9
82
9
0
0

Hint

[Sample Explanation]

For the first query, there are two houses affected: one at $x=4$ with $3$ residents, and one at $x=7$ with $6$ residents.

When the shelter is built at $x=7$, the "inconvenience" is:

$$\left\vert 7 - 4 \right\vert \times 3 + \left\vert 7 - 7 \right\vert \times 6 = 9$$

It can be proven that $9$ is the minimum "inconvenience" among all ways to build a shelter.

---

[Constraints]

• For $100\%$ of the data:

  $1 \le n, m \le 3 \times 10 ^ 5$.

  $1 \le a \le n$, $-10 ^ 9 \le l \le r \le 10 ^ 9$, $-10 ^ 9 \le x_i, b \le 10 ^ 9$, $0 \le v_i, c \le 10 ^ 3$.

• Detailed constraints:

  Let $mx$ be the maximum absolute value among all input integers.

  Test point ID	$n, m \le$	$mx \le$	Score
  $1$	$100$		$10$
  $2$	$8 \times 10 ^ 3$	$8 \times 10 ^ 3$	$15$
  $3$		$10 ^ 9$	$5$
  $4$	$10 ^ 5$	$10 ^ 5$	$30$
  $5$		$10 ^ 9$	$10$
  $6$	$3 \times 10 ^ 5$		$30$

Translated by ChatGPT 5