## DMOPC '19 Contest 3 P5 - Festival

View as PDF

Points: 20
Time limit: 2.5s
Memory limit: 256M

Author:
Problem type

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 of these fireworks, the th of which has "colour" . In the following minutes, one of three events may occur. On the th minute, Rexzae may add a new firework that has colour , he may decide to adjust all of the fireworks he currently has set up by adding 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 . 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 . (Here, a move is defined as adding or subtracting 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 than the ones that came before.

#### Constraints

The range of the colours of the different fireworks will not exceed at any time.

There are no queries of the first or second type.

#### Input Specification

The first line contains two space-separated integers, and .
The second line contains space-separated integers, .
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 .
2 a - Rexzae adds 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 .

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 .

#### 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