21. Мобилки

В Яндексе снова стартует проект «Мобилки»! Компания набирает на трёхмесячную подготовку $n$ молодых людей, увлечённых мобильной разработкой. В начале проекта был проведён тест, где скилл участника $i$ в разработке был оценен как $a_i$, а скилл в управлении как $b_i$.

На время проекта участников необходимо разделить на две равные по количеству участников команды — разработчиков и менеджеров. Планируется сделать это таким образом, чтобы максимизировать суммарную пользу, приносимую всеми участниками. Если участнику достанется роль разработчика, его польза будет равняться $a_i$, в противном случае — $b_i$.

Но даже занятые проектом, участники находят время для получения новых знаний! Иногда участники приносят сертификаты о прохождении курсов, где сказано, что скилл участника $i$ в разработке или же в управлении увеличился на $d_i$. В таком случае может быть выгодно переформировать команды для максимизации суммарной пользы (равные размеры команд необходимо сохранить).

Ваша задача — помочь Яндексу и после рассмотрения каждого нового принесённого участником сертификата посчитать текущую суммарную пользу команд.

В первой строке входного файла дано число $n$ ($2 \leq n \leq 2 \cdot 10^5$, $n$ чётное) — количество участников проекта. Вторая строка задаёт $n$ целых чисел $a_i$ $(0 \leq a_i \leq 10^9)$ — скилл каждого из участников в разработке. Следующая строка в том же формате задаёт скилл участников в управлении $b_i$ $(0 \leq b_i \leq 10^9)$.

Следующая строка содержит целое число $m$ $(1 \leq m \leq 10^5)$ — количество принесённых участниками сертификатов. Каждая из следующих $m$ строк содержит три целых числа $num_i$, $type_i$, $d_i$ $(1 \leq num_i \leq n, 1 \leq type_i \leq 2, 1 \leq d_i \leq 10^4)$ — номер участника, тип увеличиваемого скилла ($1$ — разработка, $2$ — управление) и значение увеличения соответствующего навыка.

После обработки каждого запроса на поступление нового сертификата выведите текущую суммарную пользу всех участников.