C. Digital MEGAROOT
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have probably encountered the notion of a "digital root": for a number, you take the sum of its digits, then the sum of the digits of the obtained number, and so on, until only one digit remains. Today, the author of the problem suggests moving to a new level — the "digital MEGAROOT".

Let $$$S(x)$$$ for a digit string $$$x$$$ be the sum of all digits contained in $$$x$$$.

Let $$$N_0$$$ be the starting number, written without leading zeros as a string of $$$K$$$ digits. For every pair of integers $$$L$$$, $$$R$$$ $$$(1 \le L \le R \le K)$$$, consider the substring of digits of the number $$$N_0$$$ from position $$$L$$$ to position $$$R$$$ inclusive and compute $$$S$$$ of that substring (that is, the sum of the digits in it). The number $$$N_1$$$ is defined as the sum of the values $$$S(N_0[L..R])$$$ over all pairs $$$(L, R)$$$, $$$1 \le L \le R \le K$$$.

Then the process is repeated: from $$$N_1$$$, by the same rule (all substrings of its digits are considered and their digit sums are added), $$$N_2$$$ is built; from $$$N_2$$$, $$$N_3$$$ is built; and so on — an infinite sequence of numbers $$$N_0, N_1, N_2, N_3, \ldots$$$ is obtained.

The digital MEGAROOT of the number $$$N_0$$$ is the minimum number among the entire infinite sequence $$$N_0, N_1, N_2, \ldots$$$. It can be shown that for any starting number $$$N_0$$$, this value is finite.

However, something is still missing... The author will perform $$$Q$$$ update queries on the number $$$N$$$ (which always remains a string of $$$K$$$ digits without leading zeros). Each query changes exactly one digit of the number $$$N$$$ at a given position; all changes are preserved and affect all subsequent queries.

You need to output the digital MEGAROOT of the initial number $$$N$$$, as well as the digital MEGAROOT after each of the $$$Q$$$ update queries.

Input

The first line contains one integer $$$K$$$ $$$(1 \le K \le 2 \cdot 10^5)$$$ — the number of digits in the number $$$N$$$.

The second line contains $$$K$$$ digits forming the initial number $$$N$$$ (without leading zeros).

The third line contains one integer $$$Q$$$ $$$(1 \le Q \le 2 \cdot 10^5)$$$ — the number of update queries.

The fourth line contains $$$Q$$$ integers $$$P_1, P_2, \ldots, P_Q$$$ $$$(1 \le P_i \le K)$$$ — the positions of the digit changed in the $$$i$$$-th query.

The fifth line contains $$$Q$$$ integers $$$D_1, D_2, \ldots, D_Q$$$ $$$(0 \le D_i \le 9)$$$ — the new value of the digit in the $$$i$$$-th query: in the $$$i$$$-th query, the digit at position $$$P_i$$$ is replaced by $$$D_i$$$.

It is guaranteed that if $$$P_i = 1$$$, then $$$D_i \ge 1$$$ (that is, the number $$$N$$$ never gets a leading zero).

Output

Print $$$Q + 1$$$ integers $$$R_0, R_1, \ldots, R_Q$$$ $$$(0 \le R_i \le 10^{18})$$$ in one line separated by spaces: $$$R_0$$$ is the digital MEGAROOT of the number $$$N$$$ before any queries, and $$$R_i$$$ for $$$i \ge 1$$$ is the digital MEGAROOT of the number $$$N$$$ after applying the first $$$i$$$ update queries.

It is guaranteed that the answer always exists and is unique; there is no need to output any special value in case of no answer.

Example
Input
5
14974
4
1 2 1 4
3 7 7 0
Output
6 18 8 4 18
Note

In the first example, $$$K = 5$$$, $$$N_0 = 14974$$$. Let us compute its digital MEGAROOT:

  • $$$N_0 = 14974$$$:
    • substrings of length $$$1$$$: $$$1 + 4 + 9 + 7 + 4 = 25$$$
    • substrings of length $$$2$$$: $$$(1 + 4) + (4 + 9) + (9 + 7) + (7 + 4) = 45$$$
    • substrings of length $$$3$$$: $$$(1 + 4 + 9) + (4 + 9 + 7) + (9 + 7 + 4) = 54$$$
    • substrings of length $$$4$$$: $$$(1 + 4 + 9 + 7) + (4 + 9 + 7 + 4) = 45$$$
    • substring of length $$$5$$$: $$$1 + 4 + 9 + 7 + 4 = 25$$$
    • $$$N_1 = 25 + 45 + 54 + 45 + 25 = 194$$$
  • $$$N_1 = 194$$$:
    • substrings of length $$$1$$$: $$$1 + 9 + 4 = 14$$$
    • substrings of length $$$2$$$: $$$(1 + 9) + (9 + 4) = 23$$$
    • substring of length $$$3$$$: $$$1 + 9 + 4 = 14$$$
    • $$$N_2 = 14 + 23 + 14 = 51$$$
  • $$$N_2 = 51$$$:
    • substrings of length $$$1$$$: $$$5 + 1 = 6$$$
    • substring of length $$$2$$$: $$$5 + 1 = 6$$$
    • $$$N_3 = 6 + 6 = 12$$$
  • $$$N_3 = 12$$$:
    • substrings of length $$$1$$$: $$$1 + 2 = 3$$$
    • substring of length $$$2$$$: $$$1 + 2 = 3$$$
    • $$$N_4 = 3 + 3 = 6$$$
  • starting from $$$N_4$$$, all subsequent terms are equal to $$$6$$$: $$$N_4 = N_5 = N_6 = \ldots = 6$$$.

The digital MEGAROOT is the minimum among $$$14974, 194, 51, 12, 6, 6, 6, \ldots$$$, that is, $$$6$$$. This value is output as $$$R_0$$$.

Next, let us see how the number $$$N$$$ changes after the update queries (the changes accumulate):

  • after the first query ($$$P_1 = 1$$$, $$$D_1 = 3$$$) the number becomes $$$N = 34974$$$; the corresponding sequence is: $$$34974, 204, 18, 18, \ldots$$$; the MEGAROOT is $$$18$$$;
  • after the second query ($$$P_2 = 2$$$, $$$D_2 = 7$$$) the number becomes $$$N = 37974$$$; the sequence is: $$$37974, 228, 38, 22, 8, \ldots$$$; the MEGAROOT is $$$8$$$;
  • after the third query ($$$P_3 = 1$$$, $$$D_3 = 7$$$) the number becomes $$$N = 77974$$$; the sequence is: $$$77974, 248, 46, 20, 4, \ldots$$$; the MEGAROOT is $$$4$$$;
  • after the fourth query ($$$P_4 = 4$$$, $$$D_4 = 0$$$) the number becomes $$$N = 77904$$$; the sequence is: $$$77904, 192, 45, 18, 18, \ldots$$$; the MEGAROOT is $$$18$$$.

The final answers are $$$6, 18, 8, 4, 18$$$.