시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)279534835.036%

문제

음이 아닌 $N$자리 10진수 정수 $A$와 $B$가 있다. 단, 각 수의 앞부분에 불필요한 0이 있을 수도 있다. 이때 $N+1$자리 정수 $C = A + B$를 생각하자. 마찬가지로 $A+B$의 값이 $N+1$자리가 안 될 경우 앞에 불필요한 0을 채워 $N+1$자리로 만든다.

$Q$개의 쿼리를 순서대로 처리해야 한다. 각 쿼리는 다음 중 하나이다.

  • A i d: $A$의 오른쪽에서부터 $i$번째 자리 숫자를 $d$로 바꾼다.
  • B i d: $B$의 오른쪽에서부터 $i$번째 자리 숫자를 $d$로 바꾼다.

각 쿼리를 수행할 때마다 $C = A+B$를 다시 계산하고, $C$의 각 자리 숫자 중 몇 개의 숫자가 바뀌었는지 출력하시오.

입력

첫째 줄에는 $N$과 $Q$가 주어진다. ($1 \leq N, Q \leq 300\ 000$)

둘째 줄에는 $A$, 셋째 줄에는 $B$가 주어진다.

다음 $Q$줄에는 한 줄에 하나씩 쿼리가 주어진다. 모든 쿼리에서 $1 \leq i \leq N$, $0 \leq d \leq 9$이다. 

출력

각 쿼리를 수행할 때마다 $C = A+B$를 다시 계산하고, $C$의 각 자리 숫자 중 몇 개의 숫자가 바뀌었는지 출력한다.

예제 입력 1

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

예제 출력 1

2
4
2

노트

쿼리를 실행하기 전과 각 쿼리를 실행한 후의 계산식은 차례로 다음과 같다.

  • $09905 + 80000 = 089905$
  • $09905 + 80005 = 089910$
  • $09995 + 80005 = 090000$
  • $09995 + 90005 = 100000$