Два наименьших

Дан массив. Запросы: найти два наименьших элемента на отрезке (если наименьшее значение встречается дважды, оба они — ответ) и присвоить элементу новое значение.

В первой строке $n$ ($2 \le n \le 10^5$). Во второй — $n$ чисел $a_i$ ($|a_i| \le 10^9$). В третьей — $m$ ($1 \le m \le 10^5$). Далее $m$ строк: q l r ($1 \le l < r \le n$) — два наименьших на отрезке, u i x — присвоить $a_i = x$.

Для каждого запроса q выведите на отдельной строке два числа по неубыванию.