В первой строке содержится одно число N (1 ≤ N ≤ 10^6) – количество элементов в массиве. В следующей строке находится N целых, неотрицательных чисел, не превосходящих 10^9 – сами элементы массива. Затем следует число M (1 ≤ M ≤ 10^5) – количество запросов. Затем М строк, первое число в каждой из которых означает тип запроса: если оно равно единице, то далее следует единственное число x, и Шарику надо было найти два числа l и r, такие, что максимум на промежутке [l; r], был равен x. Если же тип запроса равен двум, то далее следует два числа pos и val и это значит, что элемент массива, стоящий на позиции pos, теперь изменен и он стал равен значению val. Далее для каждого запроса с номером один содержится по строке с двумя числами l и r – ответы Шарика.