# Product of numbers

Easy

Execution time limit is 1 second

Runtime memory usage limit is 122.486 megabytes

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

Input #1

Answer #1

Input #2

Answer #2

Submissions 233

Acceptance rate 21%