You are given an array \(A\) that contains \(N\) numbers and \(M\) queries. The queries are of the following two types:
- \(update\) \(position\) \(value \): Update the number at position \(a_{position}\) with \(value\).
- \(get\space l\space r\space k\space\): Write all the numbers from \(a_l\) to position \(a_r\) inclusive without spaces. You are required to print the \(k^{th}\) digit in this sequence. If there are fewer digits in the sequence, print -1.
Input format
- The first line contains two numbers \(N\) and \(M\).
- The second line contains \(N\) numbers denoting the array \(A\).
- From the third line to \(M\) + 2 line, the queries are explained.
Output format
Print a response for each get queries. Refer to the explanation for a better understanding of the problem statement.
Constraints
\(1≤N,M≤2*10^5\)
\(0≤a[i],value≤2*10^9\)
\(1≤l≤r≤N\)
\(1≤position≤N\)
\(1≤k≤2*10^9\)
Our first queries is of type get. If you write out all the numbers from 1 to 4 positions inclusive, you get the following sequence - 110023. Position 4 in this sequence is 0.
The second update queries. Change 100 to 3.
The third queries is of type get. Sequence - 1323. 4th position - 3.
The fourth query - we have 4 digits in the sequence, 4 < 100 - output -1.
The fifth queries is 13235. We have 2 for 3 positions.
