Product of numbers

Given integers A[1], A[2], ..., A[n] and number m.

Choose such subset of numbers A[1], A[2], ..., A[n] 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 A[1], A[2], ..., A[n] (0 ≤ A[i] ≤ 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 B[1], B[2], ..., B[k] - the indexes of chosen numbers. The indexes must be pairwise different. If there are multiple answers with maximum p, print any of them.

Examples