Запросы на максимум в диапазоне

Вам дан массив из n элементов и q запросов. Существует два типа запросов:

1. Получить максимальное значение на указанном отрезке.

2. Обновить элемент массива по заданной позиции.

Ваша задача — обрабатывать эти запросы эффективно.

Входные данные

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 100 000), которые обозначают количество элементов в массиве и количество запросов соответственно.

Вторая строка содержит n разделённых пробелами целых чисел (), которые образуют начальное состояние массива.

Далее следует q строк, каждая из которых описывает один запрос:

1. Для запросов на максимум в диапазоне: строка начинается с числа 1, за которым идут два целых числа и (), указывающие границы отрезка [], где нужно найти максимальное значение.

2. Для запросов на обновление массива: строка начинается с числа 2, за которым следуют два целых числа и (), обозначающие позицию элемента для обновления и его новое значение.

Выходные данные

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

Примеры