The economic situation in Byteotia is tragic – at least according to Professor Bajterowicz. He decided to draw public attention to this issue and commissioned Bajtazar's company to install a large display in the center of the capital, which will show the current public debt of Byteotia.

Bajtazar was tasked with writing the software for the display. The device consists of $n$ decimal digits. The difficulty lies in the fact that the display software receives two numbers with at most $n-1$ digits: the internal (domestic) debt of Byteotia and the external (foreign) debt of Byteotia. The display is intended to show the sum of these two numbers.

The displayed number must be updated in real-time. Help Bajtazar and write a program that allows for the following operations: changing the $i$-th digit of the internal debt, changing the $i$-th digit of the external debt, * querying the $i$-th digit of the total debt.

Input

The first line of the input contains two integers $n$ and $z$ ($2 \le n \le 100\,000$, $1 \le z \le 100\,000$), representing the length of the display and the number of operations to perform.

The second line contains an integer representing the initial value of Byteotia's internal debt as a string of $n-1$ digits (the string may contain leading zeros). The third line contains the initial value of the external debt in the same format.

The next $z$ lines contain descriptions of the operations. Each of these lines is in one of three formats: W i c – an operation to change the $i$-th digit of the internal debt to $c$ ($1 \le i < n$, $0 \le c \le 9$), Z i c – an operation to change the $i$-th digit of the external debt to $c$ (constraints as above), * S i – a query for the $i$-th digit of the total debt ($1 \le i \le n$).

Digits are numbered from the right side (from the least significant digit) to the left.

Output

For each S operation from the input, print one line containing a single digit $c$ ($0 \le c \le 9$) which is the answer to the query.

Examples

Input 1

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

Output 1

4
1
0
2

Note

Explanation of the example: Initially, the public debt of Byteotia is $7341 + 150 = 7491$, so its third digit (from the right) is $4$. After the first change, we have $7041 + 150 = 7191$, so the third digit is $1$.

Test cases

• Test 1: random test with $n = 10, z = 100$;
• Test 2: random test with $n = z = 5000$;
• Test 3: $n = z = 100\,000$; random test satisfying the condition of the second subtask;
• Test 4: $n = z = 100\,000$; the first number is $10^{n-1} - 1$, the second is $0$; operations change the first digit of the second number and query the $n$-th digit of the sum.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.