Сегодня у Филиппа и Авроры свадьба, на которую приглашены все феи Топких Болот. Аврора слегка заскучала и решила понаблюдать за общением фей.
Исходно на свадьбе находится $$$n$$$ фей, Аврора пронумеровала их от $$$1$$$ до $$$n$$$. Фея номер $$$i$$$ характеризуется своей общительностью — целым неотрицательным числом $$$a_i$$$.
За время наблюдения, Аврора видела $$$q$$$ интересных моментов. Во время $$$j$$$-го из них происходило событие одного из трех типов:
Аврору очень интересует, насколько интенсивно феи общаются. Для этого она хочет после каждого из событий определять суммарный уровень общительности всех фей, присутствующих на свадьбе. Помогите Авроре справиться с этой нелегкой задачей.
В первой строке даны два целых числа $$$n$$$ и $$$q$$$ — количество фей, исходно находящихся на свадьбе, и количество интересных моментов в наблюдении Авроры ($$$1 \le n, q \le 100\,000$$$).
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ — значения общительности фей, исходно находящихся на свадьбе ($$$1 \le a_i \le 10^9$$$).
В следующих $$$q$$$ строках даны описания интересных моментов. Каждая из них начинается с целого числа $$$t_j$$$ — типа события ($$$t_j \in \{1, 2, 3\}$$$).
После каждого события выведите сумму значений общительности всех фей, находящихся на свадьбе.
6 5 2 3 9 5 6 6 1 3 3 5 2 2 3 2 2 7
34 37 31 27 23