На вулиці \(n\) будинків під номерами \(1,2,…,n\). У кожному будинку є піцерія та квартира.

Ціна піци в будинку \(k\) дорівнює \(p_k\). Якщо ви замовляєте піцу з корпусу \(а\) в корпус \(b\), її ціна (з доставкою) становить \(p_a+|a−b|\).

Ваше завдання — обробити два типи запитів:

• Ціна піци \(p_k\) у будівлі \(k\) стає \(x\).
• Ви знаходитесь у будівлі \(k\) і хочете замовити піцу. Яка мінімальна ціна?

Формат вхідних даних

У першому рядку вводу два цілих числа \(n\) і \(q\): кількість будівель і запитів.

У другому рядку \(n\) цілих чисел \(p_1,p_2,…,p_n\): початкова ціна піци в кожній будівлі.

Нарешті, є \(q\) рядків, які описують запити. Кожен рядок має значення «1 k x» або «2 k».

Обмеження

• \(1≤n,q≤2*10^5\)
• \(1≤p_i,x≤10^9\)
• \(1≤k≤n\)

Формат вихідних даних

Виведіть відповідь для кожного запиту типу 2.

Приклад вхідних даних

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

Приклад вихідних даних

5
4