C. Числовой КОРНИЩЕ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам, вероятно, встречалось понятие «числового корня»: для числа берётся сумма его цифр, затем сумма цифр полученного числа, и так далее, пока не останется одна цифра. Сегодня автор задачи предлагает выйти на новый уровень — «числовой КОРНИЩЕ».

Пусть $$$S(x)$$$ для строки цифр $$$x$$$ — это сумма всех цифр, входящих в $$$x$$$.

Пусть $$$N_0$$$ — стартовое число, записанное без ведущих нулей как строка из $$$K$$$ цифр. Для каждой пары целых чисел $$$L$$$, $$$R$$$ $$$(1 \le L \le R \le K)$$$ рассмотрим подотрезок цифр числа $$$N_0$$$ с позиции $$$L$$$ по позицию $$$R$$$ включительно и вычислим $$$S$$$ от этого подотрезка (то есть сумму входящих в него цифр). Число $$$N_1$$$ определяется как сумма величин $$$S(N_0[L..R])$$$ по всем парам $$$(L, R)$$$, $$$1 \le L \le R \le K$$$.

Далее процесс повторяется: из $$$N_1$$$ по тому же правилу (рассматриваются все подотрезки его цифр и суммируются их суммы цифр) строится $$$N_2$$$, из $$$N_2$$$ строится $$$N_3$$$, и так далее — получается бесконечная последовательность чисел $$$N_0, N_1, N_2, N_3, \ldots$$$

Числовым КОРНИЩЕМ числа $$$N_0$$$ называется минимальное число среди всей бесконечной последовательности $$$N_0, N_1, N_2, \ldots$$$. Можно показать, что для любого стартового числа $$$N_0$$$ данное значение является конечным.

Хотя всё равно чего-то не хватает... Автор будет выполнять над числом $$$N$$$ (которое всегда остаётся строкой из $$$K$$$ цифр без ведущих нулей) $$$Q$$$ запросов изменения. Каждый запрос изменит ровно одну цифру числа $$$N$$$ на заданной позиции; все изменения сохранятся и повлияют на все последующие запросы.

Требуется вывести числовой КОРНИЩЕ исходного числа $$$N$$$, а также числовой КОРНИЩЕ после каждого из $$$Q$$$ запросов изменения.

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

В первой строке содержится одно целое число $$$K$$$ $$$(1 \le K \le 2 \cdot 10^5)$$$ — количество цифр в числе $$$N$$$.

Во второй строке содержатся $$$K$$$ цифр, образующих изначальное число $$$N$$$ (без ведущих нулей).

В третьей строке содержится одно целое число $$$Q$$$ $$$(1 \le Q \le 2 \cdot 10^5)$$$ — количество запросов изменения.

В четвёртой строке содержатся $$$Q$$$ целых чисел $$$P_1, P_2, \ldots, P_Q$$$ $$$(1 \le P_i \le K)$$$ — позиции цифры, изменяемой в $$$i$$$-м запросе.

В пятой строке содержатся $$$Q$$$ целых чисел $$$D_1, D_2, \ldots, D_Q$$$ $$$(0 \le D_i \le 9)$$$ — новое значение цифры в $$$i$$$-м запросе: в $$$i$$$-м запросе цифра на позиции $$$P_i$$$ заменяется на $$$D_i$$$.

Гарантируется, что если $$$P_i = 1$$$, то $$$D_i \ge 1$$$ (то есть число $$$N$$$ никогда не получает ведущий ноль).

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

Выведите $$$Q + 1$$$ целых чисел $$$R_0, R_1, \ldots, R_Q$$$ $$$(0 \le R_i \le 10^{18})$$$ в одной строке через пробел: $$$R_0$$$ — числовой КОРНИЩЕ числа $$$N$$$ до каких-либо запросов, а $$$R_i$$$ при $$$i \ge 1$$$ — числовой КОРНИЩЕ числа $$$N$$$ после применения первых $$$i$$$ запросов изменения.

Гарантируется, что ответ всегда существует и единственен; выводить какое-либо специальное значение для случая отсутствия ответа не требуется.

Пример
Входные данные
5
14974
4
1 2 1 4
3 7 7 0
Выходные данные
6 18 8 4 18
Примечание

В первом примере $$$K = 5$$$, $$$N_0 = 14974$$$. Вычислим его числовой КОРНИЩЕ:

  • $$$N_0 = 14974$$$:
    • подотрезки длины $$$1$$$: $$$1 + 4 + 9 + 7 + 4 = 25$$$
    • подотрезки длины $$$2$$$: $$$(1 + 4) + (4 + 9) + (9 + 7) + (7 + 4) = 45$$$
    • подотрезки длины $$$3$$$: $$$(1 + 4 + 9) + (4 + 9 + 7) + (9 + 7 + 4) = 54$$$
    • подотрезки длины $$$4$$$: $$$(1 + 4 + 9 + 7) + (4 + 9 + 7 + 4) = 45$$$
    • подотрезок длины $$$5$$$: $$$1 + 4 + 9 + 7 + 4 = 25$$$
    • $$$N_1 = 25 + 45 + 54 + 45 + 25 = 194$$$
  • $$$N_1 = 194$$$:
    • подотрезки длины $$$1$$$: $$$1 + 9 + 4 = 14$$$
    • подотрезки длины $$$2$$$: $$$(1 + 9) + (9 + 4) = 23$$$
    • подотрезок длины $$$3$$$: $$$1 + 9 + 4 = 14$$$
    • $$$N_2 = 14 + 23 + 14 = 51$$$
  • $$$N_2 = 51$$$:
    • подотрезки длины $$$1$$$: $$$5 + 1 = 6$$$
    • подотрезок длины $$$2$$$: $$$5 + 1 = 6$$$
    • $$$N_3 = 6 + 6 = 12$$$
  • $$$N_3 = 12$$$:
    • подотрезки длины $$$1$$$: $$$1 + 2 = 3$$$
    • подотрезок длины $$$2$$$: $$$1 + 2 = 3$$$
    • $$$N_4 = 3 + 3 = 6$$$
  • начиная с $$$N_4$$$ все следующие члены равны $$$6$$$: $$$N_4 = N_5 = N_6 = \ldots = 6$$$.

Числовым КОРНИЩЕМ является минимум среди $$$14974, 194, 51, 12, 6, 6, 6, \ldots$$$, то есть $$$6$$$. Это значение выводится как $$$R_0$$$.

Далее рассмотрим, как изменяется число $$$N$$$ после запросов изменения (изменения накапливаются):

  • после первого запроса ($$$P_1 = 1$$$, $$$D_1 = 3$$$) число становится $$$N = 34974$$$; соответствующая последовательность: $$$34974, 204, 18, 18, \ldots$$$; КОРНИЩЕ равен $$$18$$$;
  • после второго запроса ($$$P_2 = 2$$$, $$$D_2 = 7$$$) число становится $$$N = 37974$$$; последовательность: $$$37974, 228, 38, 22, 8, \ldots$$$; КОРНИЩЕ равен $$$8$$$;
  • после третьего запроса ($$$P_3 = 1$$$, $$$D_3 = 7$$$) число становится $$$N = 77974$$$; последовательность: $$$77974, 248, 46, 20, 4, \ldots$$$; КОРНИЩЕ равен $$$4$$$;
  • после четвёртого запроса ($$$P_4 = 4$$$, $$$D_4 = 0$$$) число становится $$$N = 77904$$$; последовательность: $$$77904, 192, 45, 18, 18, \ldots$$$; КОРНИЩЕ равен $$$18$$$.

Итоговыми ответами являются $$$6, 18, 8, 4, 18$$$.