To prepare for his village's annual festival, Rexzae plans on putting on a display of fireworks. According to the village's spiritual beliefs, each firework is associated with a particular number, which they call its "colour". Currently, he has already set up $N$ of these fireworks, the $i$th of which has "colour" $c_i$. In the following $Q$ minutes, one of three events may occur. On the $j$th minute, Rexzae may add a new firework that has colour $d_j$, he may decide to adjust all of the fireworks he currently has set up by adding $a_j$ to all of their colours, or he might want to know the minimum cost for setting up a fireworks display that has a festivity of $k_j$. The cost for this fireworks display is the minimum number of moves that it will take for Rexzae to make all of his fireworks have a colour that is a multiple of $k_j$. (Here, a move is defined as adding or subtracting $1$ from the colour of a single firework.) Since Rexzae is greedy, each subsequent query of the third type must have a strictly larger value of $k_j$ than the ones that came before.

Constraints

In all subtasks,
$1\le N,Q\le 300000$
$-{10}^6\le a_j\le {10}^6$
$-{10}^{12}\le c_i,d_j\le {10}^{12}$
$1\le k_j\le {10}^{12}$
The range of the colours of the different fireworks will not exceed $200000$ at any time.

Subtask 1 [20%]

$1\le N,Q\le 2000$

Subtask 2 [30%]

There are no queries of the first or second type.

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, $N$ and $Q$.
The second line contains $N$ space-separated integers, $c_1,c_2,\dots ,c_N$.
$Q$ lines will follow, each of which will be in the form of one of the following:

1 d - Rexzae adds a new firework with colour $d$.
2 a - Rexzae adds $a$ to the colour of all of his fireworks.
3 k - Rexzae wants to know the minimum cost for setting up a fireworks display that has a festivity of $k$.

Note: Rexzae does not actually change the colours of his fireworks during a k operation.

Output Specification

For each query of the third type, output the minimum cost for setting up a fireworks display that has a festivity of $k_j$.

Sample Input

5 9
1 3 5 7 9
3 1
3 2
2 -3
3 3
1 14
2 5
3 5
3 7
3 10

Sample Output

0
5
3
7
12
14