有两个非负的 $N$ 位十进制整数 $A$ 和 $B$。设整数 $C = A + B$，它有 $N + 1$ 位。请注意，位数是固定的，因此整数可能包含前导零。

按顺序处理以下 $Q$ 次查询。每次查询为以下格式之一：

• A i d：将 $A$ 中从右往左数第 $i$ 位（最低位为第 $1$ 位）数字修改为 $d$。
• B i d：将 $B$ 中从右往左数第 $i$ 位（最低位为第 $1$ 位）数字修改为 $d$。

对于每次查询，重新计算整数 $C = A + B$，并输出在应用最新查询后，$C$ 中发生改变的数位个数。查询是累积的。

输入格式

第一行包含两个整数 $N$ 和 $Q$（$1 \le N, Q \le 300\,000$）。

第二行包含一个 $N$ 位十进制整数 $A$，表示为一个数字字符串。

第三行包含一个 $N$ 位十进制整数 $B$，表示为一个数字字符串。

接下来的 $Q$ 行，每行包含一个上述格式的查询。对于所有查询，满足 $1 \le i \le N$ 且 $0 \le d \le 9$。

输出格式

对于每次查询，输出由于应用该查询而导致 $C$ 中发生改变的数位个数。

样例

输入样例 1

5 3
09905
80000
B 1 5
A 2 9
B 5 9

输出样例 1

2
4
2