Three from Prostokvashino 2
- *Matroskin, I've learned how to build a segment tree.*
- *Sharik, you'd be better off building a new doghouse instead of doing silly things.*
- *Well, Matroskin, I've already shown Uncle Fyodor the code. You can check it in the previous task, and now I'll show you a new function—making updates.*
"'cpp int update(int v, int left, int right, int pos, int val) if (left == right) t[v] = val; return 0; int mid = (left + right) / 2; if (pos <= mid) update(v * 2, left, mid, pos, val); else update(v * 2 + 1, mid + 1, right, pos, val); t[v] = max(t[v * 2], t[v * 2 + 1]); return 0; "'
- *Alright, Sharik, since you've written the function, listen. I'll give you an array consisting of* **N** *non-negative numbers and a set of queries of one of two types: if the query type is one, then there will be one number* **p**, *and you need to find two numbers* **l** *and* **r** *(**1** ≤ **l** ≤ **r** ≤ **N**), such that the function called as follows*
"'cpp get_max(1, 1, N, l, r) "'
*returns a value equal to* **p**. *If there are several such pairs, output the one with the smallest* **l**. *If there are still several, output the one with the smallest* **r**. *If there are no such pairs, output the string* "**Error**". *If the query type is two, then two numbers* **x**, **y** *follow and you need to run the function as follows*
"'cpp update(1, 1, N, x, y) "'
*Can you handle such a task? You can assume that at the very beginning the function*
"'cpp build(1, 1, N) "'
*from the previous task was called.*
- *I'll try, Matroskin.*
Input
The first line contains a single number **N** (**1** ≤ **N** ≤ **10^6**) — the number of elements in the array. The second line contains **N** non-negative numbers not exceeding **10^9** — the elements of the array. Then follows the number **M** (**1** ≤ **M** ≤ **10^5**) — the number of queries. After that, there are **M** lines, each containing the first number — the type of query, followed by the query description, consisting of one or two numbers.
Output
For each query of type **1**, output the answer to the task.