Hay ~n~ edificios en una calle, numerados ~1,2,\dots,n~. Cada edificio tiene una pizzería y un apartamento. El precio de la pizza en el edificio ~k~ es ~p_k~. Si pides una pizza del edificio ~a~ al ~b~, su precio (con entrega a domicilio) es ~p_a+|a-b|~.

Tu tarea consiste en procesar dos tipos de consultas:

1. El precio de la pizza ~p_k~ en el edificio ~k~ se convierte en ~x~.
2. Estás en el edificio ~k~ y quieres pedir una pizza. ¿Cuál es el precio mínimo?

Entrada

• La primera línea de entrada tiene dos enteros ~n~ y ~q~: el número de edificios y consultas.
• La segunda línea tiene ~n~ enteros ~p_1,p_2,\dots,p_n~: el precio inicial de la pizza en cada edificio.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada línea es "~1~ ~k~ ~x~" o "~2~ ~k~".

Salida

Imprima la respuesta para cada consulta de tipo 2.

Restricciones

• ~1 \leq n,q \leq 2 \cdot 10^5~
• ~1 \leq p_i, x \leq 10^9~
• ~1 \leq k \leq n~

Ejemplo de Entrada

6 3
8 6 4 5 7 5
2 2
1 5 1
2 2

Ejemplo de Salida

5
4