Public Debt Digit Query

Professor Bajterowicz warned that the economic situation in Bajtocja is far from optimistic. To alert the public, the Bajtazara company was asked to install a giant digital display in the capital. This display shows the country’s current public debt, which is the sum of two parts: the domestic debt and the international debt.

Each of the two debts is represented as a sequence of decimal digits (each having a fixed length L). Note that each debt can have at most L digits. The displayed number is the sum of the two debt values. Over time the debts change. Your task is to write the software for the display that supports the following three types of operations:

• Type 1: Update the digit at a specified position of the domestic debt.
• Type 2: Update the digit at a specified position of the international debt.
• Type 3: Query the digit (in decimal) at a specified position of the sum of the two debts.

For the purpose of this problem, the digits in each number are indexed from the right (i.e. the rightmost digit is position 1, the next is position 2, and so on). When performing a query, if the sum does not have a digit in that position, treat it as 0.

The update operations change exactly one digit in the respective number immediately. The sum is recomputed using the standard addition algorithm with carries. In other words, if we denote the domestic debt by \(A = a_{L}a_{L-1}\cdots a_1\) and the international debt by \(B = b_{L}b_{L-1}\cdots b_1\) (with \(a_1\) and \(b_1\) being the units digits), then the sum is computed by processing from right to left using the recurrence:

\(s_i = a_i + b_i + c_{i-1}, \quad d_i = s_i \bmod 10, \quad c_i = \lfloor s_i/10 \rfloor\)

where \(c_0 = 0\). A query of type 3 on position \(p\) should output \(d_p\).

inputFormat

The first line contains two space-separated integers L and Q where L is the length of the debt numbers, and Q is the number of operations.

The second line contains a string of L digits representing the initial domestic debt.

The third line contains a string of L digits representing the initial international debt.

Each of the following Q lines describes an operation in one of the following formats:

• For an update on domestic debt: 1 pos d (set the digit at position pos of the domestic debt to digit d).
• For an update on international debt: 2 pos d (set the digit at position pos of the international debt to digit d).
• For a query: 3 pos (output the digit at position pos of the sum of the two debts).

Note: Positions are 1-indexed from the right (i.e. the unit digit is at position 1).

outputFormat

For each query (operation of type 3), output a single line with the corresponding digit from the sum of the two debts.

sample

5 5
01234
56789
3 1
1 2 9
3 2
2 5 8
3 5

3
8
8

</p>