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\)