Задачі
Морська кадриль
Морська кадриль
\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
У вихідний файл для кожного переходу виведіть сумарну масу танцюристів, що перейшли.
Вхідні дані #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
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 ...