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$