Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Magic Multiplying Machine
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 825Accepted: 282
Case Time Limit: 2000MSSpecial Judge


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 different tunes and after that declares whether player has won the game.
The algorithm for determining whether the player has won is the following. If the player has pulled some real subset S of {1, 2, . . .N} of levers, her score is the product of numbers that these levers are markedwith, taken modulo M (if the player has pulled no levers, her score is 1):
score =Πi∈Sai mod M

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 contains two integer numbers N and M (1 <= N <= 10 000, 2 <= M <= 1 000). The second line of the input file contains N integer numbers ranging from 1 to M -- a1, a2, . . . aN.


On the first line of the output file print one integer number -- the score that should be obtained to win the game. On 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.

Sample Input

4 6
1 2 3 4

Sample Output

1 4


Northeastern Europe 2002, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator