1D Spreadsheet

You have a summer internship at a large software company. Your assigned project is a new application: a 1D spreadsheet.

A 1D spreadsheet is an array of $n$ cells numbered from 1 to $n$. Cell $i$ either contains an integer $a_i$ or a link to another cell $l_i$, in which case cell $i$ is linked to cell $l_i$. Cyclic link dependencies are not allowed. At no moment is there a sequence of cells $i_1, i_2, \ldots, i_k$ where $i_1$ is linked to $i_2$, ..., and $i_k$ is linked to $i_1$.

The value of a cell is defined as follows. If cell $i$ contains a number $a_i$, then $value(i) = a_i$. Otherwise, $value(i) = value(l_i)$. To evaluate a cell, follow the chain of links from it until you reach a cell that contains a number. Since there are no cycles, $value(i)$ is uniquely defined for every cell $i$ at all times.

Bill, a colleague, added a range sum feature. Users can ask for $\sum_{i = l}^{r} value(i)$ and can change cell contents. Testing showed that Bill's implementation is slow. Your task is to write a program that processes a sequence of queries on the spreadsheet faster.

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$), the number of cells and the number of queries.

The second line contains $n$ integers $a_1, \ldots, a_n$ ($-10^4 \le a_i \le 10^4$), the initial cell values. Initially no cell contains a link.

Each of the next $q$ lines is one of the following queries.

• set i x: cell $i$ is assigned the number $x$ ($-10^4 \le x \le 10^4$).
• link i j: cell $i$ is assigned a link to cell $j$.
• sum l r: compute $\sum_{i = l}^{r} value(i)$.

It is guaranteed that no cyclic dependencies occur at any point in time.

For each sum l r query, print the answer on its own line, in the same order as the queries appear in the input.