Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Defeat in Final Battle

By iamSadee · Limits 1s, 256 MB · Custom Checker

Sifatul Islam is a great fan of Iron man. He is planning to make a suit for iron man. The suit can set a power K. Then choose a subset S of indices of enemies and calculate the sum of Poweri where i is elements of subset S. It can kill all the enemy of the subset S if the sum is divided by K. The only disadvantages of the suit is that it can be used one time only.

The AI Friday has information on N enemies(1-based index) and their Power.

He is busy in making the suit. You help him out by answering how many enemies maximum can be killed by the suit and indices of enemies of the subset S?

Input

First-line contains 2 integer N number of enemies and K power of Suit.
Next line contains N integers describing Poweri
1<=N<=2,00,000
0<=Poweri<=1018
1<= K<=2,00,000
min(N,K) <= 100

Output

First-line contains the maximum number of enemies the suit can kill.
The next line contains the resulting indices of the enemy separated by spaces.\

If there are multiple solution possible of resulting indices, you may output any.

Sample

InputOutput
5 3
1 2 1 2 3
5
1 2 3 4 5 

For This case , Maximum length of subset is 5. Subset S={1,2,3,4,5}
Sum of power of the indices =1+2+1+2+3 = 9.

9 is divided by 3 .


Discussion

Statistics


40% Solution Ratio

YouKnowWhoEarliest, Jul '20

EgorKulikovFastest, 0.2s

YouKnowWhoLightest, 94 MB

steinumShortest, 734B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.