Segment Tree – Range Minimum Query

Problem statement

A sensor network publishes the smallest reading across selected stretches of its line of stations. Individual readings may be corrected between queries, so the network needs a data structure that updates a point and retrieves a range minimum efficiently. Your task Build a segment tree supporting update index value and min left right. Updates assign a value; min returns the smallest value in the inclusive range. Important details All indices are zero-based. A query must use current values after earlier updates. Duplicate minima may occupy different stations, so updating one does not necessarily change the answer. Aim for O(n) construction and O(log n) per operation. Worked example For [5, 2, 7], min 0 2 returns 2. After update 1 9, min 0 2 returns 5.

Input format

First line: n q. Next line: n readings. Next q lines: update index value or min left right.

Output format

Print one answer per min query, or EMPTY if there are none.

Constraints

1 <= n, q <= 100000; -1000000000 <= readings <= 1000000000; all indices and inclusive ranges are valid.

Sample input

3 3
5 2 7
min 0 2
update 1 9
min 0 2

Sample output

2
5