Descripción

Los precios de la vivienda han estado subiendo y la Agencia de Recaudación de Impuestos del Condado Virtual necesita ayuda para hacer un seguimiento de los precios.

Tarea

Suponemos que las casas en el condado virtual (VC) están numeradas del ~1~ al ~n~, es decir, los números de las casas son ~1, 2, 3, ..., n~. VC realiza un seguimiento de los precios de la vivienda a medida que suben y le gustaría saber el precio total para diferentes secciones del condado, por ejemplo, el precio total para las casas ~4~ a ~15~.

Entrada

La primera línea de entrada contiene un número entero, ~n~ (~1 \le n \le 500000~), que indica el número de casas en VC. Cada una de las siguientes ~n~ líneas de entrada contiene un número entero (entre ~1~ y ~10^9~, inclusive) que indica el precio inicial de una casa; primer entero es el precio de la primera casa, segundo entero es el precio de la segunda casa, etc.

Después de la información de precio inicial para todas las casas, la entrada tendrá un conjunto de transacciones (operaciones) a procesar. Esta sección de la entrada comienza con un número entero, ~t~ (~1 \le t \le 10^5~), indicando el número de transacciones. Cada una de las siguientes ~t~ líneas de entrada contiene una transacción a ser procesada. Habrá dos tipos de transacciones:

• Actualizar transacción: esta línea de entrada comienza con la letra ~U~ en la primera columna, seguida de un espacio, seguido de un número de casa válido, seguido de un espacio, seguido de un número entero (entre ~1~ y ~10^9~, ambos inclusive), indicando el incremento en el precio de esa casa.

• Recuperar transacción: esta línea de entrada comienza con la letra ~R~ en la primera columna, seguida por un espacio, seguido de un número de casa inicial válido, seguido de un espacio, seguido de un número de casa final válido. Se solicita el precio total de esta gama. Asumir que el número de la casa final no será menor que el número de la casa inicial, es decir, el rango solicitado es válido.

Salida

No se requiere ningún resultado para las transacciones de actualización. Para cada transacción de recuperación, genere una línea separada que proporciona el precio total del rango solicitado.

Ejemplo de Entrada

5
100
200
150
300
250
8
R 2 4
U 2 20
U 3 40
R 2 4
R 1 5
U 2 10
U 4 100
R 1 5

Ejemplo de Salida

650
710
1060
1170