Регистры для Кевина

Кевин снова хочет проучить грабителей. Для этого он решил собрать электронную ловушку. Одна из ее частей --- это арифметическое логическое устройство (АЛУ). АЛУ производит все арифметические операции, которыми мы привыкли пользоваться в наших любимых языках программирования.

В этой задаче с помощью АЛУ потребуется складывать два $n$-битных числа. АЛУ состоит из регистров. Регистр --- это устройство, которое хранит в себе число.

Есть несколько типов регистров. Регистр типа $x$ может содержать в себе числа от $0$ до $2^x-1$. АЛУ должно состоять из регистров одного типа $t$, причем $t$ не задано и выбирается Кевином. Кевин может купить регистры любого типа в любом количестве.

Сложение происходит следующих образом: $n$ бит в порядке от младших к старшим обоих чисел разбиваются на отрезки длины $2^t$, кроме, возможно, последнего. Всего получается $\left \lceil{\frac{n}{2^t}} \right \rceil $ отрезков. Биты одного отрезка обоих чисел образуют два новых числа. Сложение этих чисел происходит в одном регистре. Регистры нумеруются от младших к старшим. Сначала происходит сложение в первом регистре, затем во втором и так далее. Если произошло переполнение некоторого регистра, то есть результат превышает $2^t-1$, то происходит перенос в следующий регистр. Если с учетом этого переноса в следущем регистре произошло переполнение, то происходит перенос в следующий регистр, и так далее.

Перенос --- это самая затратная по времени операция. Для каждого типа регистров известно время, которое он тратит на перенос бита. Можно считать, что сложение в одном регистре происходит мгновенно.

В продаже имеются регистры $k$ типов, неограниченное количество каждого типа. От вас требуется определить, регистры какого типа следует установить на АЛУ, чтобы достичь минимального времени исполнения.

Задача также осложняется тем, что эти числа могут меняться в зависимости от конструкции устройства.

В результате сборки устройства происходит $m$ изменений: некоторый бит некоторого числа меняется на противоположный.

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

Обратите внимание, что после ответа на запрос измененный бит не меняет свое значение обратно.

В первой строке находятся два натуральных числа $n$, $k$ ($1 \le n \le 10^5$, $1 \le k \le 17$) --- количество бит в обоих числах и количество типов регистров, имеющихся в продаже.

В следующих двух строках находятся два числа в двоичной системе счисления, возможно с ведущими нулями. Каждое состоит ровно из $n$ бит. Каждое число дано от старших битов к младшим.

В следующих $k$ строках находится описание типов регистров, имеющихся в продаже --- два целых числа $h_i$, $p_i$ ($1 \le 2^{h_i} \le n$, $1 \le p_i \le 10\,000$) --- тип регистра и время, которое занимает перенос при использовании этого типа регистров. Все $h_i$ различны.

В следующей строке находится $m$ ($1 \le m \le 10^5$) --- количество запросов на изменение.

В следующих $m$ строках находятся запросы на изменение бит чисел --- два целых числа $a_j$, $b_j$ ($1 \le a_j \le 2, 0 \le b_j < n$) --- номер числа, и номер разряда числа. Самый младший разряд имеет номер $0$.

На каждый запрос изменения бита выведите минимальное время, которое потребуется для сложения двух чисел, при оптимальном выборе типа регистра.