You sleep while we work: due to technical reasons Codeforces may be unavailable on May 22 on time interval 01:00-03:00 (MSK).
×

No tags yet

No tag edit access

time limit per test: 0.5 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard input

output: standard output

output: standard output

Well known Las-Vegas casino "Big Jo" has recently introduced the new playing machine, called Magic Multiplying Machine (MMM). MMM has N levers and one big red button. Each lever is marked with some integer number ranging from 1 to M, thus i-th lever is marked with number ai.

A player who wishes to play on MMM inserts a coin into a special slot. After that she chooses some levers and pulls them. After she has made her choice, she presses the big red button. MMM blinks all its lights, rings its bells, plays diRerent tunes and after that declares whether the player has won the game.

The algorithm for determining whether the player has won is the following. If the player has pulled some subset S in {1, 2, ... ,N} of levers, her score is the product of numbers that these levers are marked with, taken modulo M (if the player has pulled no levers, her score is 1):

The player has won the game if her score is maximal possible for the given machine.

Given the description of some MMM determine which levers should be pulled to win the game.

A player who wishes to play on MMM inserts a coin into a special slot. After that she chooses some levers and pulls them. After she has made her choice, she presses the big red button. MMM blinks all its lights, rings its bells, plays diRerent tunes and after that declares whether the player has won the game.

The algorithm for determining whether the player has won is the following. If the player has pulled some subset S in {1, 2, ... ,N} of levers, her score is the product of numbers that these levers are marked with, taken modulo M (if the player has pulled no levers, her score is 1):

The player has won the game if her score is maximal possible for the given machine.

Given the description of some MMM determine which levers should be pulled to win the game.

The first line of the input file contains two integer numbers 1 <= N <= 10000 and 2 <= M <= 1 000. The second line contains N integer numbers a1, a2, ..., aN ranging from 1 to M.

In the first line of the output file print one integer number - the score that should be obtained to win the game. In the second line print in ascending order the numbers of levers that should be pulled to obtain this score (levers are numbered starting from one). If there are several solutions, output any one.

Input

Sample input #1

4 6

1 2 3 4

Sample input #2

4 4

4 4 4 4

4 6

1 2 3 4

Sample input #2

4 4

4 4 4 4

Output

Sample output #1

4

1 4

Sample output #2

1

4

1 4

Sample output #2

1

Author: | Andrew Lopatin, Nikolay Durov |

Resource: | ACM ICPC 2002-2003 NEERC, Northern Subregion |

Date: | November, 2002 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2019 02:57:51 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|