Sea Quadrille#723
– First of all, the Gryphon began, – everyone lines up on the seashore...
– In two rows! shouted the Mock Turtle. – Seals, salmon, sea turtles and all the others. And as soon as the shore is cleared of jellyfish...
– It's not that easy, added the Gryphon.
– Small groups of dancers need to periodically move from one row to the other... – the Mock Turtle continued.
– Holding a lobster by the hand! shouted the Gryphon.
– Yes, but the main thing is to learn to quickly calculate the total mass of dancers who move. – the Mock Turtle continued without pause. – After all, there can be up to such transitions in one dance.
– No, I'd rather just learn to dance the quadrille, Alice decided, – let the quick calculations be left to someone else.
The first line contains the number , 1 \le N \le 100000. The second line contains exactly integers – the masses of the dancers in the first row, and the third line contains exactly integers – the masses of the dancers in the second row. All masses do not exceed and are listed in the order of the dancers' positions in their rows.
The next line contains the number , 1 \le M \le 100000, which is the number of transitions.
Each of the following lines contains integers: , , , . These mean that from row number (X=1 or X=2) to row number 1+|X-2| the dancers from positions through must move, and in the opposite row they must occupy positions from K+1 through K+R-L+1. All input data are correct: there is no need to move non-existent dancers or assign them to non-existent positions, and in each row the dancers always stand in a continuous line without any gaps.
For each transition, output the total mass of the dancers who moved.
Example 1