Problems
Marine quadrille (RU)
Marine quadrille (RU)
\textit{-- Это, должно быть, очень красивый танец, -- робко заметила Алиса.}
\textit{-- Хочешь посмотреть? -- спросил Черепаха Квази.}
\textit{-- Очень, -- сказала Алиса.}
\textit{-- Вставай, -- приказал Грифону Квази. -- Покажем ей первую фигуру. Ничего, что тут нет омаров... Мы и без них обойдемся.}
Приключения Алисы в стране чудес (перевод Н.М. Демуровой)
\includegraphics{https://static.e-olymp.com/content/f5/f514c9473984376c51095befa95076802de7c2ca.jpg}
-- \textit{Значит, ты не имеешь понятия, как принято танцевать морскую кадриль с омарами.}
-- \textit{Нет, не имею}, -- вздохнула Алиса. -- \textit{А что это за танец?}
-- \textit{Прежде всего}, -- начал Грифон, -- \textit{все выстраиваются в ряд на морском берегу}...
-- \textit{В два ряда!} -- закричал Черепаха Квази. -- \textit{Тюлени, лососи, морские черепахи и все остальные. И как только очистишь берег от медуз...}
-- \textit{А это не так-то просто}, -- вставил Грифон.
-- \textit{Надо периодически небольшим группам танцоров переходить из одного ряда в другой... -- }продолжал Черепаха Квази.
-- \textit{Взяв за ручку омара!} -- закричал Грифон.
-- \textit{Да, но самое главное -- это научиться очень быстро вычислять массу перешедших танцоров. -- }Не унимался Квази. -- \textit{Ведь за один танец таких переходов может быть до }\textbf{100000}\textit{.}
-- \textit{Ну уж лучше я кадриль научусь танцевать}, -- решила Алиса, -- \textit{а быстрым счётом пусть другие занимаются.}
\InputFile
В первой строке записано число \textbf{N}, \textbf{1} ≤ \textbf{N} ≤ \textbf{100000}. Во второй строке записано ровно \textbf{N} чисел -- массы танцоров в первом ряду, в третьей строке записано ровно \textbf{N} чисел -- массы танцоров во втором ряду. Все массы не превосходят \textbf{10000} и указываются в том порядке, в котором танцоры стоят в своих рядах.
На следующей строке записано число \textbf{M}, \textbf{1} ≤ \textbf{M} ≤ \textbf{100000} -- количество переходов.
В каждой из следующих строк записано по \textbf{4} числа -- \textbf{X}, \textbf{L}, \textbf{R}, \textbf{K}. Они означают, что из ряда с номером \textbf{X} (\textbf{X}=\textbf{1} или \textbf{X}=\textbf{2}) в ряд с номером \textbf{1}+|\textbf{X--2}| должны перейти танцоры с \textbf{L}-й позиции по \textbf{R}-ю и при этом в противоположном ряду они должны занять позиции с \textbf{K+1} по \textbf{K+R--L+1}. Все входные данные корректны, то есть не придется переставлять несуществующих танцоров на несуществующие позиции и в каждом из рядов танцоры будут стоять четко в ряд, один за другим, без свободных мест.
\OutputFile
В выходной файл для каждого перехода выведите суммарную массу переходящих танцоров.
Input example #1
39 2820 7509 4206 5112 3435 8960 114 8272 4339 3721 6608 9368 8979 7527 9540 6138 3312 4134 2186 8856 8543 6135 2027 4661 9338 487 7094 8323 7032 5484 302 7339 2784 9790 9171 9696 2368 2919 3029 5500 4256 7194 6938 5315 3692 270 3979 6735 3373 1489 9863 3787 7829 270 2239 2555 7558 4193 4029 2827 6601 9585 4922 2547 2726 4664 9324 5870 5859 7292 5387 2189 895 8664 5406 8320 1068 4983 644 2 1 17 18 1 32 40 17 1 6 45 15 1 5 7 11 2 18 49 1 1 29 33 33 2 18 45 31 1 23 57 19 2 19 20 3 1 19 19 15 1 6 13 2 1 4 14 12 2 66 67 4 2 13 49 7 1 35 40 20 1 3 33 5 2 7 70 7 1 56 60 3 1 1 32 2 1 33 35 18 2 30 41 8 2 10 31 43 2 2 8 44 2 1 1 29 2 3 3 23 2 2 2 67 1 29 42 0 2 2 8 39 1 13 13 7 2 3 5 15 1 21 71 1 2 22 44 2 1 9 19 33 2 34 46 19 2 8 25 35 2 4 14 57 2 1 4 12 1 26 62 0 1 12 40 19 2 33 44 2 1 1 14 33 2 8 33 4 1 16 17 27 1 25 30 22 2 19 38 13 2 10 29 35 1 52 53 7 1 9 10 8 1 59 61 7 2 7 12 15 1 1 2 5 1 63 63 10 1 59 64 5 2 20 20 37 2 7 18 48 2 2 3 42 1 41 54 1 1 45 45 8 2 15 19 38 1 19 28 8 2 3 25 38 ...
Output example #1
75284 40640 227272 9383 178693 29903 149983 182310 8962 4256 48928 60725 15417 189714 30227 164875 337223 23601 164442 19011 49182 125114 36763 7558 4339 8272 67581 27568 9324 6980 281067 125938 55664 64926 94721 72555 30210 194345 154285 68094 78220 136001 5987 19025 76964 106235 7390 14290 17024 35256 15180 8320 38570 8979 77742 13729 87973 4922 28279 39549 122678 4029 7094 16680 2027 7509 11198 212888 86084 18133 13729 77946 46069 10036 38798 15668 127666 147432 85876 3029 111611 77715 154260 9171 67010 60900 33081 47110 74912 23162 24246 203721 49895 9338 41025 2919 25669 3787 121566 29547 5859 28638 200365 44341 9773 142715 8131 73518 14131 42852 58654 42746 7194 30403 28396 8131 26130 7509 24462 7829 114028 3435 27510 15608 84108 126390 18952 7527 109936 41534 24838 41834 122756 7527 8919 85755 62891 72953 15822 86757 38618 43650 45853 45949 17857 9863 41353 15135 42416 41353 9540 36907 186878 42109 270 56992 8960 36476 10842 56027 11288 30544 7292 83603 79574 50643 17096 137845 ...