406715: GYM102503 L Arnis Ball

Jason Vincent Ben Eric is the cook for his school's arnis team! He has a row of $$$n$$$ boxes, one for each member of the team, and he's filling the boxes with balls of pastillas. Inspired by a different game involving desserts in boxes, he decides to play a game to put desserts into the boxes, to make his job a little more fun.

Initially, the $$$i$$$th box contains $$$A_i$$$ balls. Each of the boxes can be either open or closed. Jason can do three different actions to the boxes of pastillas, which are named after three of his favorite sweet dishes.

The first is turon. Turn off what is on, and TUR-ON what is off! When Jason does a turon move, he selects two integers $$$L$$$ and $$$R$$$. For all boxes between the $$$L$$$th and the $$$R$$$th boxes, inclusive, he closes the boxes that are open, and he opens the boxes that are closed.

The next is puto. If a box is open, PUT-O more desserts! When Jason does a puto move, he selects two integers $$$L$$$ and $$$R$$$, and an integer $$$v$$$. For all open boxes between the $$$L$$$th and the $$$R$$$th boxes, inclusive, he adds $$$v$$$ balls.

The last is taho. TA-HOW many desserts are there? When Jason does a taho move, he selects two integers $$$L$$$ and $$$R$$$. For all boxes between the $$$L$$$th and the $$$R$$$th boxes, inclusive, he counts the number of balls, and then adds them.

You are given the $$$m$$$ moves that Jason does. Help Jason check his work by computing the answer to all of his taho moves.

The first line contains two space-separated integers $$$n$$$ and $$$m$$$.

The next line contains $$$n$$$ space-separated integers such that the $$$i$$$th integer is $$$A_i$$$, the initial number of balls in the $$$i$$$th box.

The line after that contains $$$n$$$ space-separated integers, with each equal to 0 or 1. If the $$$i$$$th integer is 0, then the $$$i$$$th box is initially closed, and if the $$$i$$$th number is 1, then $$$i$$$ is initially open.

Following this are $$$m$$$ lines, each representing one of Jason's moves. Each line will be of one of three forms,

1. 1 L R represents a turon move with integers $$$L$$$ and $$$R$$$. The number $$$1$$$ is chosen because it's tur-ONE.

2. 2 L R v represents a puto move with integers $$$L$$$, $$$R$$$, and $$$v$$$. The number $$$2$$$ is chosen because it's pu-TWO.

3. 3 L R represents a taho move with integers $$$L$$$ and $$$R$$$. The number $$$3$$$ is chosen because people can throw taho in THREE different directions.

For each taho move Jason makes, print a single line containing the answer he should have computed, assuming all of his moves were done correctly.

$$$1 \le n, m \le 3.2\times 10^5$$$

$$$1 \le A_i, v \le 10^6$$$

$$$1 \le L \le R \le n$$$

Subtask 1 (11 points):

$$$1 \le n,m \le 3000$$$

Subtask 2 (11 points):

All boxes are initially open.

There are no turon moves.

All taho moves will have $$$L=R$$$.

Subtask 3 (11 points):

All boxes are initially open.

There are no turon moves.

Subtask 4 (11 points):

There are no turon moves.

All taho moves will have $$$L=R$$$.

Subtask 5 (14 points):

There are no turon moves.

Subtask 6 (14 points):

All taho moves will have $$$L=R$$$.

Subtask 7 (14 points):

$$$1 \le n,m \le 10^5$$$

Subtask 8 (14 points):

No additional constraints.

5 6
1 2 4 8 16
1 0 1 0 1
3 2 4
2 1 5 6
3 2 4
1 1 5
2 1 5 7
3 2 4

14
20
34

Here, the boxes initially contain $$$1, 2, 4, 8, 16$$$ balls, respectively. Furthermore, the 1st, 3rd, and 5th boxes are initially open, while the 2nd and 4th boxes are initially closed.

The following queries then occur, in order:

1. The sum of the boxes in [2,4] is equal to $$$2+4+8=14$$$.
2. All boxes in [1,5] that are open—which are the 1st, 3rd and 5th boxes—each get 6 balls added to them. The 2nd and 4th boxes are closed, so they are ignored. Thus, the boxes now contain $$$7, 2, 10, 8, 22$$$ balls, respectively.
3. The sum of the boxes in [2,4] is now equal to $$$2+10+8=20$$$.
4. We now perform a turon move on the boxes in range $$$[1,5]$$$. So, now the 1st, 3rd, and 5th boxes are closed while the 2nd and 4th boxes are now open.
5. All boxes in [1,5] that are open—this time, these are the 2nd and 4th boxes—each get 7 balls added to them. Thus, the boxes now contain $$$7, 9, 10, 15, 22$$$ balls, respectively.
6. The sum of the boxes in [2,4] is finally equal to $$$9+10+15=34$$$.