Funmondi Contest!

There is a contest being held on Funmondi named ‘Funmondi Inter School Programming Contest’. You are one of the head organizers of this contest. So you have to keep track of so many things. One of them is how many school student is currently present in the venue.

Each school has an id number. There are n schools participating in this contest. You know how many students from each school are currently present at the venue. But the contestant can leave or enter the venue at any moment as the gate is open. But you will get to know a student from which school is checking in or checking out in the venue.

This is a huge problem to keep track of, right? So you decided to build a program that will handle all the information for you and keep the record of how many schools are currently present at this moment.

Input

In the first line, You will receive n and q, which indicates how many schools are going to participate in this contest and query respectively.

The next line will contain n different numbers a1, a2, a3, ..., an (0 ≤ ai ≤ 100000). ai represents the number of students from the ith school.

In the next q (1 ≤ q ≤ 200000) lines, you will receive two types of queries.

1 v: One student from vth (1 ≤ v ≤ n ≤ 200000) school left the venue.

2 v: One student from vth school entered the venue.

It is guaranteed that all operations are valid.

Output

After each query, you will print how many schools are currently present in the venue.

Sample

Input	Output
8 4 5 6 7 8 0 0 1 4 2 5 2 6 1 7 1 1	7 8 7 7
After the first query the present schools are: 1, 2, 3, 4, 5, 7, 8. After the second query the present schools are: 1, 2, 3, 4, 5, 6, 7, 8. After the third query the present schools are: 1, 2, 3, 4, 5, 6, 8. After the fourth query the present schools are: 1, 2, 3, 4, 5, 6, 8.

Huge dataset, please use faster I/O.