칠판 수 합 구하기

암산 대회의 심사위원장이 새로운 과제를 냈다. 처음에 칠판에 정수 $n$개 $a_1, a_2, \ldots, a_n$이 적혀 있다. 참가자는 그 뒤에 다음 두 종류의 명령을 수행해야 한다.

1. $i$번째 수를 지우고 그 자리에 $x$를 적는다. 그러면 수열은 $a_1, \ldots, a_{i-1}, x, a_{i+1}, \ldots, a_n$이 된다.
2. 수열을 오른쪽으로 $k$만큼 순환 이동한다. 그러면 수열은 $a_{n-k+1}, \ldots, a_n, a_1, \ldots, a_{n-k}$가 된다.

참가자는 명령을 수행할 때마다 칠판에 적힌 모든 수의 합을 구해 심사위원에게 보고해야 한다. 심사위원은 답을 확인하기 위해 요구되는 합을 직접 계산해야 한다.

첫째 줄에 처음 칠판에 적힌 정수의 개수 $n$이 주어진다 ($2 \leq n \leq 10^5$).

둘째 줄에 공백으로 구분된 정수 $n$개 $a_1, a_2, \ldots, a_n$이 주어진다 ($-10^9 \leq a_i \leq 10^9$).

셋째 줄에 수행할 명령의 개수 $q$가 주어진다 ($1 \leq q \leq 10^5$).

이어지는 $q$개의 줄에 각각 다음 형식 중 하나로 명령이 주어진다.

• 1 i x: $i$번째 수를 $x$로 바꾼다 ($1 \leq i \leq n$; $-10^9 \leq x \leq 10^9$).
• 2 k: 수열을 오른쪽으로 $k$만큼 순환 이동한다 ($1 \leq k < n$).

$q$개의 줄을 출력한다. 각 줄에는 정수 하나를 적는다. $i$번째 줄에는 처음 $i$개의 명령을 수행한 후 칠판에 적힌 수들의 합을 적는다.

답이 클 수 있으므로 64비트 정수형이 필요하다. 파스칼에서는 int64, C++에서는 long long, 자바에서는 long을 사용한다.

문제의 예시에서 처음 수열은 $4, 1, 2, 1, 5, 3$이다. 첫 번째 명령 후 수열을 오른쪽으로 3칸 이동하면 $1, 5, 3, 4, 1, 2$가 되고, 합은 $1 + 5 + 3 + 4 + 1 + 2 = 16$이다. 두 번째 명령은 세 번째 원소를 $10$으로 바꾸어 $1, 5, 10, 4, 1, 2$를 만들고, 합은 $23$이다. 세 번째 명령은 네 번째 원소를 $4$로 바꾼다. 이미 $4$이므로 수열은 바뀌지 않고 합은 $23$으로 그대로이다. 네 번째 명령은 수열을 1칸 이동하여 $2, 1, 5, 10, 4, 1$을 만들며, 합은 변하지 않는다. 다섯 번째 명령은 첫 번째 원소를 $-10$으로 바꾸어 $-10, 1, 5, 10, 4, 1$을 만들고, 합은 $-10 + 1 + 5 + 10 + 4 + 1 = 11$이다.