Background

This problem is translated from XXVIII Olimpiada Informatyczna – Stage I Licznik długu.

Problem Description

Professor Bajterowicz points out that the economic situation of Bajtocja is not optimistic right now. To warn the public, he asked the Bajtazara company to install a large display in the city center of Bajtocja’s capital, used to show the current public debt of Bajtocja.

Bajtocja’s public debt consists of two parts: domestic debt and international debt. The domestic debt and the international debt can each have at most $n-1$ decimal digits. The display shows the sum of these two debts.

As time passes, Bajtocja’s debt situation keeps changing. You now need to help the Bajtazara company complete the editing of the display software.

The software needs to perform the following three operations:

• Change the digit at a certain position of the domestic debt.
• Change the digit at a certain position of the international debt.
• Output the digit at a certain position of the total public debt.

Input Format

The first line contains two integers $n, z$, representing the number of digits the display can show and the number of operations.

The second line contains a number of length $n-1$, representing the initial value of Bajtocja’s domestic debt. This number may have leading zeros.

The third line contains a number of length $n-1$, representing the initial value of Bajtocja’s international debt. This number may have leading zeros.

The next $z$ lines each describe an operation:

• $\texttt{W}\ i \ c$ means changing the $i$-th digit of the domestic debt to $c$ ($1 \leq i \leq n-1$, $0 \leq c \leq 9$).
• $\texttt{Z}\ i \ c$ means changing the $i$-th digit of the international debt to $c$ ($1 \leq i \leq n-1$, $0 \leq c \leq 9$).
• $\texttt{S}\ i$ means outputting the value of the $i$-th digit of the total public debt ($1 \leq i \leq n-1$).

Output Format

For each $\texttt{S}$ operation, output one line with one integer representing the answer.

5 6
7341
0150
S 3
W 3 0
S 3
Z 1 9
S 1
S 3

4
1
0
2

10 100
627280304
679703557
Z 9 9
Z 2 5
S 3
S 3
W 6 2
W 9 6
Z 6 2
Z 3 9
S 7
Z 5 9
S 3
S 6
S 8
Z 3 2
W 5 1
Z 4 5
W 5 8
S 1
W 4 7
W 8 7
S 9
Z 5 7
S 8
W 5 5
S 6
W 9 9
W 8 0
S 1
S 8
W 8 7
S 9
W 2 4
W 5 7
S 4
Z 6 0
Z 8 2
W 8 2
S 2
W 5 7
W 4 7
W 1 4
W 2 9
S 3
W 8 3
W 5 2
Z 4 2
W 5 9
W 8 3
W 6 6
S 6
W 6 8
Z 7 4
S 5
W 9 9
W 9 6
S 10
W 7 8
Z 1 5
Z 3 4
S 5
S 2
W 9 9
W 3 0
Z 9 4
Z 1 1
Z 5 9
W 7 2
S 3
S 5
W 3 6
Z 4 7
S 7
Z 5 4
S 7
S 1
W 2 8
Z 1 7
W 3 6
W 8 4
S 7
Z 8 8
Z 5 0
W 8 9
W 7 1
S 2
W 2 7
S 2
W 2 5
Z 5 0
W 9 8
W 4 5
Z 2 8
S 5
S 2
Z 2 7
S 1
S 1
W 8 1
W 4 8
Z 7 2

8
8
6
2
5
0
1
6
5
5
1
8
9
2
0
6
7
6
1
6
4
5
8
6
6
5
6
4
3
0
4
1
1

Hint

[Sample Explanation #1]:

Initially, the total public debt is $7341+150=7491$, so the value of the third digit is $4$.

After operation $2$, the total public debt is $7041+150=7191$, so the value of the third digit is $1$.

After operation $4$, the total public debt is $7041+159=7200$, so the value of the first digit is $0$, and the value of the third digit is $2$.

[Constraints]:

All testdata satisfy: $2 \leq n \leq 10^5$, $1 \leq z \leq 10^5$.

Translated by ChatGPT 5