Problem Preparation

Andrew has written $n$ programming problems for a contest and now he plans to prepare them. He estimates that preparing problem $i$ takes $t_i$ minutes in total. Andrew wants to invite his friends to share the work.

He does not know how many friends will agree to help, but he wants to split the work fairly. So for problem $i$ he picks an integer $x_i$, and every friend who helps spends $x_i$ minutes on that problem. Problem $i$ is completely prepared once the total time his friends spend on it is at least $t_i$ minutes. With $k$ friends helping, $x_i$ is the smallest integer that satisfies $k \times x_i \ge t_i$.

Whenever Andrew realizes that he misjudged the difficulty of a problem, he increases or decreases $t_i$ by 1.

You are given the initial estimates $t_i$. Process $m$ queries in the given order. Each query is one of the following.

• 1 i: Andrew increases $t_i$ by 1.
• 2 i: Andrew decreases $t_i$ by 1.
• 3 k: Andrew wants to know how many minutes one friend spends preparing all $n$ problems when $k$ friends help.

The first line contains two integers $n$ and $m$, the number of problems and the number of queries. ($1 \le n, m \le 10^5$)

The second line contains $n$ integers $t_1, t_2, \dots, t_n$, where $t_i$ is Andrew's initial estimate for problem $i$. ($1 \le t_i \le 5 \times 10^5$)

Each of the next $m$ lines contains one query as two integers $q$ and $v$. If $q$ is 1, then $t_v$ increases by 1. If $q$ is 2, then $t_v$ decreases by 1. In both cases $1 \le v \le n$. If $q$ is 3, then you must report the time one friend spends when $v$ friends help. In this case $1 \le v \le 5 \times 10^5$.

After every query all values of $t_i$ stay between 1 and $5 \times 10^5$.

For every query with $q$ equal to 3, print on its own line the total time one friend spends preparing all $n$ problems, that is $x_1 + x_2 + \dots + x_n$.