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\)
5 5 1 100 2 3 5 get 1 4 4 update 2 3 get 1 4 4 get 1 4 100 get 1 5 3
0 3 -1 2
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor