В уже известном вам городе Банкополисе наконец-то появился новый банк! К сожалению, еще не до конца готова его система безопастности... Тем временем в Банкополисе появился хакер Леха, который решил протестировать систему на прочность!
В банке хранятся 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.
Так как Леха — белый хакер, то он не хочет исследовать уязвимость на реальной базе данных. Вам необходимо реализовать для Лехи похожую базу данных, способную отвечать на его запросы!
Примечание
Рассмотрим первый пример.
Первоначально последовательность имеет вид [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.