Морская кадриль - Задачи

\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 В выходной файл для каждого перехода выведите суммарную массу переходящих танцоров.

Лимит времени 3.5 секунды

Лимит использования памяти 64 MiB

Входные данные #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
...

Выходные данные #1

Автор Соболев Евгений, Соболев Дмитрий

Источник VI Open Cup Kharkov 14.03.2010