A 더하기 B 문제

JB는 A 더하기 B 문제를 푸는 기계를 얻었고, 그 동작 원리가 궁금하다. 그는 당신이 경쟁 프로그래밍에 능숙하고 Link-Cut tree, Lagrange Inversion formula, Sweepline Mo 등 여러 고급 자료구조와 알고리즘을 익혔다는 이야기를 들었다. 그래서 기계와 같은 방식으로 A 더하기 B 문제를 푸는 프로그램을 구현해 달라고 부탁한다.

기계는 $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\le10^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$번째 줄에는 $i$번째 질의 후 셋째 행의 $c_i$번째 숫자와, 이 질의로 기계의 숫자가 몇 개 바뀌는지를 공백으로 구분해 두 정수로 출력한다.

예시에서 초기 행은 01234, 56789, 58023이다.

1번째 질의 후 행은 01234, 06789, 08023이다.

2번째 질의 후 행은 01234, 01789, 03023이다.

3번째 질의 후 행은 01234, 01289, 02523이다.

4번째 질의 후 행은 01234, 01239, 02473이다.

5번째 질의 후 행은 01234, 01234, 02468이다.