E. Snowfall Statistics
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Winter is coming. To help the state prepare for the annual freak Austin winter storm, you've volunteered to build an app that visualizes historical temperature statistics.

The state has numbered its counties from $$$1$$$ to $$$C$$$, in a way that nearby counties geographically have nearby numbers. The state has also provided you with the record low temperature recorded for each county.

Users will interact with your app in two ways.

1. They can ask your app to report the lowest recorded temperature across all counties in the range $$$[L, R]$$$ inclusive. In other words, if $$$T_i$$$ is the lowest temperature recorded for county $$$i$$$, this query asks for $$$$$$\min\left(T_L, T_{L+1}, \ldots, T_{R-1}, T_R\right).$$$$$$

2. Users can report a temperature for a county. If this temperature is lower than the lowest historical temperature in that county, you should take the new value into account for all subsequent queries.

Implement the backend for an app with this functionality.

Input

The first line of input contains two space-separated integers $$$C$$$ $$$(1 \leq C \leq 50\,000)$$$ and $$$Q$$$ $$$(1 \leq Q \leq 100\,000)$$$: the number of counties in the state, and the number of times the user interacts with the app.

The next line contains $$$C$$$ space-separated integers $$$T_i$$$ $$$(-50 \leq T_i \leq 120)$$$: the record low temperature of each county in the state.

The final $$$Q$$$ lines record the user interactions with your app, in order. Each interaction has one of the following two forms:

  • QUERY $$$L$$$ $$$R$$$: asks for the lowest temperature ever recorded across countries $$$L$$$ through $$$R$$$, inclusive. $$$L$$$ and $$$R$$$ satisfy the bounds $$$1 \leq L \leq R \leq C$$$. Print this lowest temperature.
  • OBSERVED $$$i$$$ $$$T$$$: reports an observation of temperature $$$T$$$ in county $$$i$$$ $$$(1 \leq i \leq C; -50 \leq T \leq 120)$$$. Do not print anything, but take this observation into account when computing lowest recorded temperature in later queries.

It is guaranteed that at least one of the $$$Q$$$ interactions is of type QUERY.

Output

For each interaction of type QUERY, print the requested lowest recorded temperature across those counties (see above). Print one query result per line.

Example
Input
5 6
5 -10 15 0 -2
QUERY 1 5
OBSERVED 2 15
QUERY 1 3
OBSERVED 4 -19
OBSERVED 5 -3
QUERY 1 5
Output
-10
-10
-19