E. Запросы суммы?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Введем определение хорошего мультимножества следующим образом. Выпишем сумму всех элементов мультимножества в виде десятичного числа. Если для каждого разряда существует хотя бы одно число из мультимножества, в котором такая же цифра, как и в полученной сумме, то мультимножество хорошее, иначе плохое.

Например, мультимножество $$$\{20, 300, 10001\}$$$ — хорошее, а мультимножество $$$\{20, 310, 10001\}$$$ — плохое:

Красным отмечены те числа и разряды, в которых те же цифры, что и в сумме. Сумма первого мультимножества равна $$$10321$$$, для каждого разряда есть необходимая цифра. Сумма второго мультимножества равна $$$10331$$$, и для второго с конца разряда не сушествует числа с такой же цифрой, что делает мультимножество плохим.

Вам дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$.

Необходимо ответить на запросы к нему. Запросы могут быть двух типов:

  • $$$1~i~x$$$ — заменить $$$a_i$$$ на $$$x$$$;
  • $$$2~l~r$$$ — найти плохое подмножество мультимножества чисел $$$a_l, a_{l + 1}, \dots, a_r$$$ с минимальной суммой или сказать, что плохих подмножеств не существует.

Обратите внимание, что пустое подмножество является хорошим.

Для каждого запроса второго типа выведите наименьшую сумму плохого подмножества. Выведите -1, если не существует плохого подмножества.

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

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — количество элементов в массиве и количество запросов, соответственно.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < 10^9$$$).

В каждой из следующих $$$m$$$ строк записан запрос одного из двух типов:

  • $$$1~i~x$$$ ($$$1 \le i \le n$$$, $$$1 \le x < 10^9$$$) — заменить $$$a_i$$$ на $$$x$$$;
  • $$$2~l~r$$$ ($$$1 \le l \le r \le n$$$) — найти плохое подмножество мультимножества чисел $$$a_l, a_{l + 1}, \dots, a_r$$$ с минимальной суммой или сказать, что плохих подмножеств не существует.

Гарантируется, что есть хотя бы один запрос второго типа.

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

Для каждого запроса второго типа выведите наименьшую сумму плохого подмножества. Выведите -1, если не существует плохого подмножества.

Пример
Входные данные
4 5
300 10001 20 20
2 1 3
1 1 310
2 1 3
2 3 3
2 3 4
Выходные данные
-1
330
-1
40
Примечание

Все подмножества мультимножества $$$\{20, 300, 10001\}$$$ являются хорошими, поэтому ответ -1.

Все возможные плохие подмножества в третьем запросе: $$$\{20, 310\}$$$ и $$$\{20, 310, 10001\}$$$. С меньшей суммой — $$$\{20, 310\}$$$. Обратите внимание, что требуется найти подмножество, а не подотрезок, поэтому выбранные элементы не обязательно будут стоять рядом в массиве.

В четвертом запросе есть только пустое подножество и подмножество $$$\{20\}$$$. Оба они хорошие.

В последнем запросе есть пустое подмножество и подмножества $$$\{20\}$$$, $$$\{20\}$$$ и $$$\{20, 20\}$$$. Только $$$\{20, 20\}$$$ — плохое, его сумма равна $$$40$$$. Обратите внимание, что требуется выбрать мультимножество, поэтому оно может включать в себя одинаковые элементы.