Дан массив \(a_1, a_2, \dots, a_n\), вам нужно обработать суммарно \(q\) запросов и обновлений следующих типов:
Первая строка содержит целое число \(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\) строк каждого набора входных данных содержат запросы следующих видов:
Гарантируется, что существует хотя бы один запрос второго типа.
Сумма \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач