Sea Quadrille
"It's probably a very beautiful dance," Alice remarked awkwardly.
"Do you want to see it?" asked the Mock Turtle.
"Very much," replied Alice.
"Stand up," the Gryphon commanded the Mock Turtle. "Let's show her the first figure. It's okay that there are no lobsters here... We'll manage without them."
Adventures of Alice in Wonderland (translated by N.M. Demurova)
"You have no idea how to dance the Lobster Quadrille, do you?"
"No, I don't," Alice admitted. "And what kind of dance is it?"
"First of all," began the Gryphon, "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 you clear the shore of jellyfish..."
"It's not that easy," interjected the Gryphon.
"Small groups of dancers need to periodically move from one row to the other..." continued the Mock Turtle.
"Holding a lobster by the hand!" shouted the Gryphon.
"Yes, but the main thing is to learn to quickly calculate the mass of the dancers who moved," the Mock Turtle insisted. "After all, there can be up to 100000 such transitions in one dance."
"No, I'd rather learn to dance the quadrille," decided Alice, "and let others deal with quick calculations."
Input
The first line contains the number N, where 1 ≤ N ≤ 100000. The second line lists exactly N numbers, representing the masses of the dancers in the first row. The third line also contains exactly N numbers, representing the masses of the dancers in the second row. All masses are no greater than 10000 and are listed in the order the dancers stand in their rows.
The next line contains the number M, where 1 ≤ M ≤ 100000, indicating the number of transitions.
Each of the following lines contains 4 numbers: X, L, R, K. These specify that dancers from row X (X=1 or X=2) should move to the opposite row, from positions L to R, and take positions from K+1 to K+R–L+1 in the other row. All input data are valid, meaning there will be no attempts to move non-existent dancers to non-existent positions, and dancers in each row will stand in a continuous line without gaps.
Output
For each transition, output the total mass of the dancers who moved.