F. Леха и система безопасности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В уже известном вам городе Банкополисе наконец-то появился новый банк! К сожалению, еще не до конца готова его система безопастности... Тем временем в Банкополисе появился хакер Леха, который решил протестировать систему на прочность!

В банке хранятся n ячеек клиентов. Последовательность из n чисел a1, a2, ..., an описывает количество денег в ячейке каждого клиента. Леха желает обращаться к базе данных банка, узнавая суммарное количество денег в ячейках на промежутке последовательсти и изменяя значения в ячейках на промежутке. Через лазейку в системе хакеру Лехе доступно два вида запросов к базе данных банка:

  • 1 l r x y, означающий, что Леха может изменить каждую цифру x на цифру y во всех таких элементах ai последовательности, для которых верно l ≤ i ≤ r. Например, если в числе 11984381 цифру 8 заменить на 4, то получится число 11944341. Стоит заметить, что Леха, чтобы остаться незамеченным, никогда не изменяет цифры на 0, то есть y ≠ 0.
  • 2 l r, означающий, что Леха может запросить сумму таких элементов ai последовательности, для которых верно l ≤ i ≤ r.

Так как Леха — белый хакер, то он не хочет исследовать уязвимость на реальной базе данных. Вам необходимо реализовать для Лехи похожую базу данных, способную отвечать на его запросы!

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

В первой строке находится два целых числа n и q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105), означающих количество ячеек в банке и суммарное количество запросов Лехи соответственно.

В следующей строке записано n целых чисел a1, a2, ..., an (1 ≤ ai < 109) — числа, означающие изначальное количество денег в ячейках. Эти числа не содержал лидирующих нулей.

Каждая из последующих q строк имеет один из форматов:

  • 1 l r x y (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 9, 1 ≤ y ≤ 9), означающий, что Леха запрашивает изменить каждую цифру x на цифру y во всех таких элементах ai последовательности, для которых верно l ≤ i ≤ r;
  • 2 l r (1 ≤ l ≤ r ≤ n), означающий, что Вы должны вычислить и вывести сумму таких элементов ai последовательности, для которых верно l ≤ i ≤ r.
Выходные данные

На каждый запрос о сумме чисел на промежутке последовательности в отдельной строке выведите одно целое число — искомую сумму.

Примеры
Входные данные
5 5
38 43 4 12 70
1 1 3 4 8
2 2 4
1 4 5 0 8
1 2 5 8 7
2 1 5
Выходные данные
103
207
Входные данные
5 5
25 36 39 40 899
1 1 3 2 7
2 1 2
1 3 5 9 1
1 4 4 0 9
2 1 5
Выходные данные
111
1002
Примечание

Рассмотрим первый пример.

Первоначально последовательность имеет вид [38, 43, 4, 12, 70].

После первого изменения все цифры, равные 4, изменяются на 8 у элементов последовательности, имеющих индексы в промежутке [1; 3]. Таким образом, новая последовательность — [38, 83, 8, 12, 70].

Ответом на первый запрос суммы является сумма на промежутке [2; 4], равная 83 + 8 + 12 = 103, поэтому ответ на первый запрос суммы равен 103.

После второго изменения последовательность приобретает вид [38, 83, 8, 12, 78], а после третьего — [38, 73, 7, 12, 77].

Ответом на второй запрос суммы является 38 + 73 + 7 + 12 + 77 = 207.