Description

Freyz has a toy store in City C. The store sells $n$ kinds of toys, numbered $1,2,\dots,n$. The unit price of toy $i$ is $c_i$ yuan, and buying one unit of this toy provides happiness value $v_i$.

One day, $m$ children came to City C. According to reliable information, these children will come to the store together at certain times to buy things. Each time, the $i$-th child will bring exactly $i$ yuan ($1\leq i\leq m$).

Because some toys are especially good, every time the children will only choose toys within a specific index range.

Also, since the children were already so happy in last year’s Tsinghua programming contest that they could not stop, Freyz gave up treating them, so the children can buy toys without limits. That is, for any toy, each child can buy any non-negative integer quantity each time.

As time moves forward quickly, the popularity and prices of toys may also change.

To help you handle this information, Yazid organized it and found that there were $Q$ events in Freyz’s toy store during these days.

Each event has $3$ basic parameters $op,l,r$. Here $op$ is an integer from $1$ to $3$, representing the type of the event:

1. For an event with $op=1$, Yazid will also give you an extra parameter $d$, meaning this is a price adjustment event: increase the unit price $c$ of all toys with indices in $[l,r]$ by $d$ yuan. To prevent a unit price from exceeding $m$ yuan and making the toy never purchasable by the children, Freyz will subtract $m$ from any unit price that exceeds $m$. (It is guaranteed that $d$ is a positive integer not exceeding $m$.)

2. For an event with $op=2$, Yazid will also give you an extra parameter $b$, meaning this is a happiness modification event: increase the happiness value $v$ of all toys with indices in $[l,r]$ by $b$. (Note that $b$ may be negative.)

3. For an event with $op=3$, this is a purchase event: all $m$ children come to Freyz’s toy store and buy freely among the toys with indices in $[l,r]$.

Now, for each purchase event, you want to know:

1. The sum of the maximum total happiness that all children can obtain.

2. The xor sum of the maximum total happiness that all children can obtain (xor is the $\mathrm{xor}$ operation, i.e. the ^ operator in C++/Java/Python).

Input Format

• Line $1$: two positive integers $n,m$, representing the number of toys and the number of children.

• Line $2$: $n$ positive integers $c_1,\dots,c_n$, describing the unit price of each toy.

• Line $3$: $n$ positive integers $v_1,\dots,v_n$, describing the happiness value of each toy.

• Line $4$: one non-negative integer $Q$, representing the number of events.

• The next $Q$ lines describe all events, one per line. Each line starts with three integers $op,l,r$, as described above.

  • If $op=1$, it is followed by one extra parameter (integer) $d$, as described above.

  • If $op=2$, it is followed by one extra parameter (integer) $b$, as described above.

  • If $op=3$, there is no extra parameter.

  • It is guaranteed that $1\leq l\leq r\leq n$.

In each line, if there are multiple numbers, they are separated by a single space.

Output Format

• For each purchase event, output one line with two integers separated by a space, representing the sum of the maximum happiness all children can obtain, and the xor sum of the maximum happiness all children can obtain, in this order.

4 10
1 6 10 2
100 2333 666 300
7
3 1 4
3 1 3
1 2 4 1
3 1 4
2 2 3 -1000
2 2 3 -600
3 2 4

15165 2865
14165 2169
36630 798
4899 1273

Hint

Sample Explanation

For the $1$-st purchase event, the maximum happiness each child (in order of indices from $1$ to $10$) can obtain is: $100,300,400,600,700,2333,2433,2633,2733,2933$.

For the $2$-nd purchase event, the maximum happiness each child (in order of indices from $1$ to $10$) can obtain is: $100,200,300,400,500,2333,2433,2533,2633,2733$.

For the $3$-rd purchase event, the maximum happiness each child (in order of indices from $1$ to $10$) can obtain is: $666,1332,1998,2664,3330,3996,4662,5328,5994,6660$.

For the $4$-th purchase event, the maximum happiness each child (in order of indices from $1$ to $10$) can obtain is: $0,0,300,300,300,600,733,733,900,1033$.

With this information, you can easily compute the answers.

Constraints

It is guaranteed that $1\le n\leq 200,000$, $1\le m\leq 60$, $0\le Q\leq 30,000$.

It is guaranteed that $1\leq c_i,d\leq m$.

It is guaranteed that $0\leq v_i\leq 10^7$, $\left| b\right|\leq 10^3$.

Hint

This hint should not have existed, but the kind problem setter still wants to remind you: the sum of the maximum happiness all children can obtain may exceed the range of 32-bit signed integers.

Copyright Information

From the 2018 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2018). Thanks to Pony.ai for supporting this contest.

Solutions and other resources can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5