1차원 스프레드시트

여름 방학 동안 대형 소프트웨어 회사에서 인턴으로 일하게 되었다. 배정된 프로젝트는 새로 개발 중인 최신 애플리케이션인 1차원 스프레드시트이다.

1차원 스프레드시트는 1부터 $n$까지 번호가 붙은 $n$개의 셀로 이루어진 배열이다. 셀 $i$에는 정수 $a_i$가 들어 있거나, 다른 셀 $l_i$를 가리키는 링크가 들어 있다. 후자의 경우 셀 $i$가 셀 $l_i$에 링크되어 있다고 한다. 순환 링크는 허용되지 않는다. 즉, 어떤 시점에도 셀 $i_1$이 $i_2$에, ..., 셀 $i_k$가 $i_1$에 링크되는 셀들의 수열 $i_1, i_2, \ldots, i_k$는 존재하지 않는다.

셀의 값은 다음과 같이 정의된다. 셀 $i$에 수 $a_i$가 있으면 $value(i) = a_i$이다. 그렇지 않으면 $value(i) = value(l_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, \ldots, 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 질의마다 답을 한 줄에 하나씩, 입력에 나온 순서대로 출력한다.