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 300\,000~
~-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 ~200\,000~ 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