P10516 Data Structures

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.

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.

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 several lines, each being the answer to an Operation 3 query.

**[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