Background

Little M likes data structures very much. Unfortunately, he did not make it into the NOI Qualifier team.

Everyone has dreams, and everyone has their own wonderful life.

Problem Description

Given two sequences $a_i$ and $b_i$ of length $n$. There are three types of operations:

1. Given an interval $[l,r]$ and parameters $k,t$, for each position in the interval that satisfies $a_i\times b_i\leq k$, add $t$ to $a_i$ and add $t$ to $b_i$.
2. Given $i$ and $x,y$, set $a_i$ to $x$, and set $b_i$ to $y$.
3. Query the sum of $a_i+b_i$ over all positions in the interval.

Input Format

The first line contains two integers $n,m$, representing the number of elements in the sequences and the total number of operations.

The second line contains $n$ integers separated by spaces; the $i$-th integer is $a_i$.

The third line contains $n$ integers separated by spaces; the $i$-th integer is $b_i$.

The next $m$ lines each contain $3$ to $5$ integers, describing one operation as follows:

1. 1 l r k t: perform Operation 1 on interval $[l,r]$.
2. 2 i x y: set $a_i$ to $x$, and set $b_i$ to $y$.
3. 3 l r: output the sum over the interval $[l,r]$.

Output Format

Output several lines, each being the answer to an Operation 3 query.

5 5
23 4 3 3 7
54 29 7 1 2
1 1 5 114 1
2 2 7 9
3 1 5
3 1 2
3 3 4

122
93
18

Hint

[Sample Explanation]

After the first modification, the sequence $a_i$ is: $\left\{23,4,4,4,8\right\}$; the sequence $b_i$ is $\left\{54,29,8,2,3\right\}$.

After the second modification, the sequence $a_i$ is: $\left\{23,7,4,4,8\right\}$; the sequence $b_i$ is $\left\{54,9,8,2,3\right\}$.

[Constraints]

• For $5\%$ of the testdata, $n,m\le 5$.
• For $10\%$ of the testdata, $n,m\leq 100$.
• For $25\%$ of the testdata, $n,m\leq 5000$.
• For another $5\%$ of the testdata, there are no Operations 1 and 2.
• For another $10\%$ of the testdata, there is no Operation 1.
• For another $20\%$ of the testdata, there is no Operation 2.

For all testdata, $1\leq n,m\leq 10^5$, $0\leq a_i,b_i,k,t,x,y\leq10^5$.

Translated by ChatGPT 5