Как известно, после одной шахматной партии Сора и его сестра Широ попали в мир Дисборд, где все конфликты решаются играми. Вскоре они стали правителями людей. Однако новые обязанности их совсем не волновали, и они проводили дни напролёт, играя в любимые игры. Такой расклад не устраивал только Стефани, которая отчаянно пыталась заставить Сору взяться за свои обязанности правителя. Но Сора, как всегда, игнорировал её просьбы.
Однажды Стефани поняла, что в мире, где всё решается через игры, даже такую задачу можно решить с помощью матча. Если она сможет победить Сору в игре, то сможет заставить его выполнять обязанности короля. Проблема заключалась в том, что Сора никогда не проигрывал никому, кроме своей сестры Широ. Поэтому Стефани решила тщательно подготовиться.
Во дворце было $$$n$$$ последовательных комнат, пронумерованных от $$$1$$$ до $$$n$$$. Стефани выбрала $$$n$$$ игр, не обязательно различных, и разместила в каждой комнате по одной. Она договорилась с Сорой провести $$$q$$$ матчей — по одному в день, а также перед каждым матчем потренироваться с Широ. Широ, такая же ленивая, как и Сора, в $$$i$$$-й день просыпалась в комнате с номером $$$r_i$$$ и готова была тренировать во всех комнатах, которые находились на её пути к комнате с номером $$$l_i$$$, в которой она завтракала в $$$i$$$-й день. Формально тренировка проходила во всех комнатах отрезка $$$[l_i, r_i]$$$. После тренировки Стефани шла в комнату $$$k_i$$$, где её ждал Сора.
Сора каждый день выходил в город, а потому направлялся в сторону комнаты $$$1$$$ — выхода. Он не хочет тратить много времени на Стефани, потому готов играть с ней во всех комнатах подряд, начиная с $$$k_i$$$-й до какой-нибудь $$$t_i$$$-й ($$$t_i \leq k_i$$$) включительно, не пропуская ни одну, двигаясь по направлению к выходу.
Стефани не уверена в своих силах, а потому не будет играть с Сорой в игры, на которых не тренировалась с Широ, однако хочет попытать удачу в абсолютно каждой игре, в которую играла утром до матча. Формально Стефани будет играть только в то множество игр, которое равно множеству игр с утренней тренировки.
Сора, хоть и согласился на её условия, но игра в любой комнате требует времени, а плохая затемнённость в некоторых из них ему не нравится, ведь он не любит солнечный свет. Поэтому Сора хочет, чтобы суммарная затемнённость во всех комнатах, в которых он сыграет со Стефани, была как можно больше.
В первой строке подается целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество игр и комнат замка.
Во второй строке задано $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^5$$$) — игры, которые разложила Стефани. Одинаковые числа означают одну и ту же игру, а разные — разные.
В третьей строке задано $$$n$$$ целых чисел $$$w_i$$$ ($$$|w_i| \leq 10^9$$$) — затемнённость каждой комнаты.
В четвертой строке подается число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество дней и матчей.
В следующих $$$q$$$ строках даны числа $$$l$$$, $$$r$$$, $$$k$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq k \leq n$$$) — комнаты, где Широ завтракает, где Широ проснулась, где находится Сора в $$$i$$$-й день соответственно.
Для каждого дня, если существуют отрезки комнат с играми, удовлетворяющими требованиям Стефани, выведите наибольшую суммарную затемнённость среди всех таких отрезков. Если же таких отрезков комнат нет, и требованиям Стефани удовлетворить нельзя, то матч в этот день пропускается, в этом случае выведите Skip.
95 2 1 3 4 1 3 2 40 2 -1 1 -5 1 1 1 142 3 82 5 93 5 76 8 3
Skip 4 -2 Skip
В $$$1$$$-й день тренировка была в комнатах $$$[2, 3]$$$ на играх $$$\{2, 1\}$$$. В комнате $$$7$$$ находится игра $$$3$$$, в которую Стефани не будет играть, поэтому играть можно только во всех комнатах отрезка $$$[8]$$$, в них только одна игра $$$2$$$, и Стефани пропустит день из-за отсутствия игры $$$1$$$.
Во $$$2$$$-й день с Сорой можно сыграть в комнатах на $$$[6, 9]$$$, $$$[5, 9]$$$, $$$[4, 9]$$$, $$$[3, 9]$$$, $$$[2, 9]$$$, они удовлетворяют требования Стефани. Среди них наибольшая затемнённость достигается на $$$[6, 9]$$$ — $$$1 + 1 + 1 + 1 = 4$$$.
В $$$3$$$-й день тренировка была на играх $$$\{1, 3, 4\}$$$, потому с Сорой можно сыграть на $$$[5, 7]$$$, $$$[4, 7]$$$, $$$[3, 7]$$$, и максимальная затемнённость будет на $$$[4, 7]$$$ — $$$1 -5 + 1 + 1 = -2$$$.
В $$$4$$$-й день невозможно удовлетворить требованиям Стефани, так как нет ни одного набора с играми $$$\{1, 3, 2\}$$$.