H. Лунки с монетами

Те же лунки, что в классной задаче H, но у каждой лунки, кроме силы выброса, есть ещё и число монет. Шарик собирает монеты всех лунок, в которых побывал, включая стартовую и последнюю.

В первой строке - числа $N$ и $M$ ($1 \le N, M \le 10^5$).

Во второй - $N$ сил выброса, целых от 1 до $N$.

В третьей - $N$ чисел монет, целых от 1 до 1000.

В следующих $M$ строках - ходы: «0 a b» установить силу лунки $a$ равной $b$, либо «1 a» бросить шарик в лунку $a$.

Для каждого хода второго типа выведите два числа: номер последней лунки перед вылетом и сумму собранных монет.