A Plus B Problem

JB got a machine that solves the A Plus B Problem, and he wants to know how it works. He heard that you are proficient in competitive programming and have learned many advanced data structures and algorithms, such as Link-Cut tree, Lagrange Inversion formula, Sweepline Mo, and so on. So he asks you to implement a program that solves the A Plus B Problem the same way the machine does.

The machine consists of $3\times n$ digits. The digits of the first two rows can be changed arbitrarily, and the third row always equals the decimal sum of the first two rows. The third row keeps only the lowest $n$ digits, even if the sum has more than $n$ digits.

For example, when $n=5$, the three rows can be 01234, 56789, 58023 or 56789, 58023, 14812.

To test your function, you are given $q$ queries. In the $i$-th query, the $c_i$-th digit of the $r_i$-th row is changed to $d_i$ (the digit may stay the same). JB has no time to check your answers, so he only asks you to find the $c_i$-th digit of the third row after the query and how many digits of the machine change in that query.

The first line contains two integers $n$ and $q$ ($1\le n, q\le10^6$).

The second line contains a string of $n$ digits, representing the first row of the machine.

The third line contains a string of $n$ digits, representing the second row of the machine.

The next $q$ lines follow. The $i$-th of them contains three integers $r_i$, $c_i$, and $d_i$ ($1\le r_i \le 2$, $1\le c_i\le n$, $0\le d_i\le 9$).

Output $q$ lines. In the $i$-th line, output two integers: the $c_i$-th digit of the third row after the query, and how many digits of the machine change in the query.

In the example, the initial rows are 01234, 56789, 58023.

After the 1st query, the rows are 01234, 06789, 08023.

After the 2nd query, the rows are 01234, 01789, 03023.

After the 3rd query, the rows are 01234, 01289, 02523.

After the 4th query, the rows are 01234, 01239, 02473.

After the 5th query, the rows are 01234, 01234, 02468.