该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $n$ 的序列 $a = (a_1, a_2, …, a_N)$。

按顺序处理 $q$ 个查询。每个查询是以下两种格式之一：

• $1$ $x$ ：交换 $a_x$ 和 $a_{x+1}$ 的值。

• $2$ $l$ $r$ ：计算 $∑_{i=l}^{r}a_i$ 的值。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $(1≤t≤1000)$。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ 分别表示序列的长度和查询的次数。$(2≤n，q≤2×10^5)$

每个测试用例的第二行包含 $n$ 个整数，表示给定的序列 $(a_1, a_2, …, a_n)$，其中 $(1≤a_i≤10^4)$

每个测试用例的接下来 $q$ 行，每行表示询问，询问有两种类型，格式为：

• $1$ $x$
• $2$ $l$ $r$

约束条件：

对于第一种类型的查询，$1≤x≤n−1$

对于第二种类型的查询，$1≤l≤r≤n$

保证所有测试用例，$n$ 的总和不超过 $2×10^5$, $q$ 的总和不超过 $2×10^5$。

输出格式

对于每个测试用例，输出第二种类型的查询答案。

样例

2
4 4
2 7 1 8
1 2
2 1 2
1 1
2 2 4
8 10
22 75 26 45 72 81 47 29
2 2 7
2 6 8
2 4 4
1 2
2 1 3
1 1
2 2 4
1 2
1 4
2 1 1

3
17
346
157
45
123
142
26

样例解释

对于第一组样例：

在第 $1$个查询中，交换 $a₂$ 和 $a₃$ 的值。这使得 $a$ 变为 $(2, 1, 7, 8)$。

在第 $2$ 个查询中，计算 $a₁ + a₂$ 的值。答案是 $2 + 1 = 3$。

在第 $3$ 个查询中，交换 $a₁$ 和 $a₂$ 的值。这使得 $a$ 变为 $(1, 2, 7, 8)$。

在第 $4$ 个查询中，计算 $a₂ + a₃ + a₄$ 的值。答案是 $2 + 7 + 8 = 17$。