Введем определение хорошего мультимножества следующим образом. Выпишем сумму всех элементов мультимножества в виде десятичного числа. Если для каждого разряда существует хотя бы одно число из мультимножества, в котором такая же цифра, как и в полученной сумме, то мультимножество хорошее, иначе плохое.
Например, мультимножество \(\{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, если не существует плохого подмножества.
Выходные данные
Для каждого запроса второго типа выведите наименьшую сумму плохого подмножества. Выведите -1, если не существует плохого подмножества.
Примечание
Все подмножества мультимножества \(\{20, 300, 10001\}\) являются хорошими, поэтому ответ -1.
Все возможные плохие подмножества в третьем запросе: \(\{20, 310\}\) и \(\{20, 310, 10001\}\). С меньшей суммой — \(\{20, 310\}\). Обратите внимание, что требуется найти подмножество, а не подотрезок, поэтому выбранные элементы не обязательно будут стоять рядом в массиве.
В четвертом запросе есть только пустое подножество и подмножество \(\{20\}\). Оба они хорошие.
В последнем запросе есть пустое подмножество и подмножества \(\{20\}\), \(\{20\}\) и \(\{20, 20\}\). Только \(\{20, 20\}\) — плохое, его сумма равна \(40\). Обратите внимание, что требуется выбрать мультимножество, поэтому оно может включать в себя одинаковые элементы.
Примеры
| № | Входные данные | Выходные данные |
|
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
|