D - Rotando y Sumas

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, Python, ... (details)

Fito ha estado entrenando su memoria en los últimos días. Él se ha inventado un juego para dicho propósito. Primero, Fito se imagina $N$ enteros alineados uno al lado del otro numerados de $1$ a $N$ ($x_1, x_2, …, x_N$), después, aplica indistintamente dos tipos de operaciones:

Operación 1: Selecciona dos enteros $a$ y $b$ tal que $1 \le a \le b \le N$ y trata de recordar la suma de los elementos con índices en el intervalo $[a, b]$, es decir $x_a + x_{a+1} + … + x_b$.

Operación 2: Selecciona dos enteros $a$ y $b$ tal que $1 \le a \le b \le N$ y realiza una rotación a la derecha sobre el intervalo $[a, b]$, es decir, el elemento en la posición $a$ pasa a ocupar la posición $a+1$, el de la posición $a+1$ ocupará la posición $a+2$ y así sucesivamente hasta llegar al elemento situado en la posición $b$ que se pondrá al inicio del intervalo, o sea, en la posición $a$.

Fito tiene muy buena memoria, no obstante él necesita un juez que lo corrija si se equivoca. Él no conoce persona capaz de ocupar este rol sin equivocación, por ello, te ha pedido que lo ayudes escribiendo un programa que simule las operaciones que se le vayan ocurriendo. Su tarea consiste en dado $N$ $(1 \le N \le 100000)$ enteros $x_1, x_2, …x_N$ y un conjunto de $Q$ operaciones, simular el juego de Fito.


Input

Línea 1 : Un entero $N$ $(1 \le N \le 100000 )$, la cantidad de números pensados por Fito.
Línea 2 : $N$ enteros separados por espacio $x_1, x_2, …, x_N$ $(-10^6 \le x_i \le 10^6)$.
Línea 3 : Un entero $Q$ $(1 \le Q \le 100000)$, la cantidad de operaciones que Fito aplicará cronológicamente a la lista de N enteros.
Línea 4…Q+3 : Tres enteros por línea $k$, $a$ y $b$ $(1 \le k \le 2, 1 \le a \le b \le N)$. El valor de $k$ refleja el tipo de la operación.


Output

Línea 1… : Por cada operación de tipo 1, imprima el resultado. Note que las operaciones se irán realizando cronológicamente.

Sample test(s)

Input
7 -5 1 3 -2 0 6 4 4 2 4 7 1 1 5 2 3 6 1 4 7
Output
1 11

Hints