Given integers A1, A2, ..., An and number m.

Choose such subset of numbers A1, A2, ..., An so that their product taken modulo m is maximum.

Input

First line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 10000). Second line contains n integers A1, A2, ..., An (0 ≤ Ai ≤ 10000).

Output

Print in the first line numbers p and k - the product of chosen numbers by modulo m and the number of chosen numbers. Print in the second line k numbers B1, B2, ..., Bk - the indexes of chosen numbers. The indexes must be pairwise different. If there are multiple answers with maximum p, print any of them.