F. Range Update Point Query
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a_1, a_2, \dots, a_n$$$, вам нужно обработать суммарно $$$q$$$ запросов и обновлений следующих типов:

  • $$$1$$$ $$$l$$$ $$$r$$$ — для каждого индекса $$$i$$$ такого, что $$$l \leq i \leq r$$$, заменить значение $$$a_i$$$ на сумму цифр в $$$a_i$$$.
  • $$$2$$$ $$$x$$$ — вывести $$$a_x$$$.
Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — размер массива и количество запросов соответственно.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Следующие $$$q$$$ строк каждого набора входных данных содержат запросы следующих видов:

  • $$$1$$$ $$$l$$$ $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — означает, что для каждого индекса $$$i$$$ такого, что $$$l \leq i \leq r$$$, вам следует заменить значение $$$a_i$$$ на сумму его цифр.
  • $$$2$$$ $$$x$$$ ($$$1 \leq x \leq n$$$) — означает, что вы должны вывести $$$a_x$$$.

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

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Сумма $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите ответы на запросы второго типа, в том порядке, в котором они заданы в тесте.

Пример
Входные данные
3
5 8
1 420 69 1434 2023
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5
2 3
9999 1000
1 1 2
2 1
2 2
1 1
1
2 1
Выходные данные
6
15
1434
1
6
7
36
1
1
Примечание

В первом наборе входных данных происходят следующие изменения:

  • Изначально $$$a = [1, 420, 69, 1434, 2023]$$$.
  • Операция применяется с $$$l=2$$$, $$$r=3$$$, получаем $$$[1, \color{red}{6}, \color{red}{15}, 1434, 2023]$$$.
  • Запрошены значения с $$$x=2$$$, $$$x=3$$$, и $$$x=4$$$, выводим $$$6$$$, $$$15$$$, и $$$1434$$$.
  • Операция применяется с $$$l=2$$$, $$$r=5$$$, получаем $$$[1, \color{red}{6}, \color{red}{6}, \color{red}{12}, \color{red}{7}]$$$.
  • Запрошены значения с $$$x=1$$$, $$$x=3$$$, и $$$x=5$$$, выводим $$$1$$$, $$$6$$$, и $$$7$$$.