Морская кадриль
– Это, должно быть, очень красивый танец, – робко заметила Алиса.
– Хочешь посмотреть? – спросил Черепаха Квази.
– Очень, – сказала Алиса.
– Вставай, – приказал Грифону Квази. – Покажем ей первую фигуру. Ничего, что тут нет омаров... Мы и без них обойдемся.
Приключения Алисы в стране чудес (перевод Н.М. Демуровой)
– Значит, ты не имеешь понятия, как принято танцевать морскую кадриль с омарами.
– Нет, не имею, – вздохнула Алиса. – А что это за танец?
– Прежде всего, – начал Грифон, – все выстраиваются в ряд на морском берегу...
– В два ряда! – закричал Черепаха Квази. – Тюлени, лососи, морские черепахи и все остальные. И как только очистишь берег от медуз...
– А это не так-то просто, – вставил Грифон.
– Надо периодически небольшим группам танцоров переходить из одного ряда в другой... – продолжал Черепаха Квази.
– Взяв за ручку омара! – закричал Грифон.
– Да, но самое главное – это научиться очень быстро вычислять массу перешедших танцоров. – Не унимался Квази. – Ведь за один танец таких переходов может быть до 100000.
– Ну уж лучше я кадриль научусь танцевать, – решила Алиса, – а быстрым счётом пусть другие занимаются.
Входные данные
В первой строке записано число N, 1 ≤ N ≤ 100000. Во второй строке записано ровно N чисел – массы танцоров в первом ряду, в третьей строке записано ровно N чисел – массы танцоров во втором ряду. Все массы не превосходят 10000 и указываются в том порядке, в котором танцоры стоят в своих рядах.
На следующей строке записано число M, 1 ≤ M ≤ 100000 – количество переходов.
В каждой из следующих строк записано по 4 числа – X, L, R, K. Они означают, что из ряда с номером X (X=1 или X=2) в ряд с номером 1+|X–2| должны перейти танцоры с L-й позиции по R-ю и при этом в противоположном ряду они должны занять позиции с K+1 по K+R–L+1. Все входные данные корректны, то есть не придется переставлять несуществующих танцоров на несуществующие позиции и в каждом из рядов танцоры будут стоять четко в ряд, один за другим, без свободных мест.
Выходные данные
В выходной файл для каждого перехода выведите суммарную массу переходящих танцоров.