Sobre un arreglo de \(n\) enteros se hacen \(q\) operaciones de dos tipos:

• 1 i v: el elemento de la posición \(i\) pasa a valer \(v\).
• 2 i j: informar la suma de los elementos entre las posiciones \(i\) y \(j\), ambas incluidas.

Cada operación debe costar \(O(\log n)\).

Entrada

La primera línea tiene \(n\) y \(q\) \((1 \le n, q \le 10^5)\). La segunda tiene el arreglo inicial. Siguen \(q\) líneas con las operaciones. Las posiciones se cuentan desde \(0\), \(i \le j\) en las consultas y todos los valores tienen valor absoluto a lo más \(100\).

Salida

Para cada operación de tipo 2, una línea con la suma.

Ejemplo 1

Entrada

3 3
1 3 5
2 0 2
1 1 2
2 0 2

Salida

9
8