你获得了一个绝佳的机会，在暑期进入一家大型软件公司实习。你被分配的项目是一个全新的尖端应用程序——一维电子表格。

一维电子表格是一个包含 $n$ 个单元格的数组，编号从 $1$ 到 $n$。单元格 $i$ 可以包含一个整数 $a_i$ 或者指向另一个单元格 $l_i$ 的链接（在这种情况下，我们称单元格 $i$ 链接到单元格 $l_i$）。不允许存在循环链接依赖，即在任何时刻，不存在单元格序列 $i_1, i_2, \dots, i_k$，使得单元格 $i_1$ 链接到 $i_2$，$\dots$，且单元格 $i_k$ 链接到 $i_1$。

每个单元格都可以被求值以产生其值，定义如下：如果单元格 $i$ 包含一个数字 $a_i$，则 $value(i) = a_i$；否则 $value(i) = value(l_i)$。也就是说，要对一个单元格求值，必须沿着链接链一直追踪，直到到达一个包含数字的单元格为止。由于不允许循环依赖，在任何时刻，每个单元格 $i$ 的 $value(i)$ 都可以唯一确定。

你的同事 Bill 刚刚为电子表格开发了一项新功能——区间求和。启用此功能后，用户可以查询“求 $\sum_{i=l}^r value(i)$”，也可以更改单元格的内容。然而，经过一些性能测试，发现 Bill 的实现非常缓慢。你的任务是优化此功能。编写一个程序来处理一维电子表格的一系列查询。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $q$ ($1 \le n, q \le 2 \cdot 10^5$)，分别表示电子表格中的单元格数量和需要处理的查询数量。

第二行包含 $n$ 个空格分隔的整数 $a_1, \dots, a_n$ ($-10^4 \le a_i \le 10^4$)，表示单元格的初始值。最初，没有任何单元格包含链接。

接下来的 $q$ 行包含查询描述，格式如下：

• “set $i$ $x$” —— 将单元格 $i$ 设置为包含数字 $x$ ($-10^4 \le x \le 10^4$)。
• “link $i$ $j$” —— 将单元格 $i$ 设置为包含指向单元格 $j$ 的链接。
• “sum $l$ $r$” —— 计算 $\sum_{i=l}^r value(i)$。

保证在任何时刻都不会出现循环依赖。

输出格式

按输入顺序输出“sum $l$ $r$”查询的答案，每行一个。

样例

样例输入 1

5 7
1 2 3 4 5
sum 1 5
link 3 5
link 1 3
link 4 2
sum 1 5
set 5 -1
sum 1 5

样例输出 1

15
19
1