Byteman ha estado entrenando su memoria en los últimos días. Él se ha inventado un juego para dicho propósito. Primero, Byteman se imagina ~N~ enteros alineados uno al lado del otro numerados de ~1~ a ~N (x_1x_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~.

Byteman 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 Byteman.

Entrada

Línea 1: Un entero ~N (1 \le N \le 100000)~, la cantidad de números pensados por Byteman. 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 Byteman 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.

Salida

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

Entrada

7
-5 1 3 -2 0 6 4
4
2 4 7
1 1 5
2 3 6
1 4 7

Salida

1
11