JB 拥有一台可以解决“A Plus B Problem”的机器，并对它的工作原理感到好奇。他听说你精通竞赛编程，学习过诸如 Link-Cut Tree、拉格朗日反演、扫描线莫队等许多高级数据结构和算法。因此，他请求你帮助实现一个程序，使其能像那台机器一样解决“A Plus B Problem”。

这台机器由 $3 \times n$ 个数字组成。前两行的数字可以任意更改，第三行始终等于前两行的十进制和。即使和超过了 $n$ 位，第三行也仅保留最低的 $n$ 位。

例如，当 $n = 5$ 时，这三行可以是 “01234”、“56789”、“58023”，或者 “56789”、“58023”、“14812”。

为了测试你的函数，你将收到 $q$ 次查询。在第 $i$ 次查询中，第 $r_i$ 行的第 $c_i$ 位数字被更新为 $d_i$（数字可能保持不变）。由于数字太多，JB 没有时间检查你的答案，他只要求你在每次查询后，求出第三行的第 $c_i$ 位数字，以及该查询导致机器中发生了多少位数字的变化。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^6$)。

第二行包含一个由 $n$ 个数字组成的字符串，表示机器的第一行。

第三行包含一个由 $n$ 个数字组成的字符串，表示机器的第二行。

接下来的 $q$ 行中，第 $i$ 行包含三个整数 $r_i$、$c_i$ 和 $d_i$ ($1 \le r_i \le 2, 1 \le c_i \le n, 0 \le d_i \le 9$)。

输出格式

输出 $q$ 行。在第 $i$ 行中，输出两个整数：查询后第三行的第 $c_i$ 位数字，以及该查询导致机器中发生了多少位数字的变化。

样例

输入 1

5 5
01234
56789
2 1 0
2 2 1
2 3 2
2 4 3
2 5 4

输出 1

0 2
3 2
5 3
7 3
8 3

说明

在样例中，初始行分别为 “01234”、“56789”、“58023”。

第 1 次查询后，各行为 “01234”、“06789”、“08023”。

第 2 次查询后，各行为 “01234”、“01789”、“03023”。

第 3 次查询后，各行为 “01234”、“01289”、“02523”。

第 4 次查询后，各行为 “01234”、“01239”、“02473”。

第 5 次查询后，各行为 “01234”、“01234”、“02468”。