Заданы целые числа A1, A2, ..., An и число m.

Выберите такое подмножество чисел A1, A2, ..., An, чтобы их произведение, взятое по модулю m, было максимально.

Входные данные

В первой строке заданы два целых числа n и m (1 ≤ n ≤ 100, 1 ≤ m ≤ 10000). Во второй строке записаны n целых чисел A1, A2, ..., An (0 ≤ Ai ≤ 10000).

Выходные данные

В первой строке выведите числа p и k - произведение выбранных чисел по модулю m и количество выбранных чисел, соответственно. Во второй строке выведите k чисел B1, B2, ..., Bk - номера выбранных чисел. Номера должны быть попарно различны. Если ответов с максимальным p несколько, можно выводить любой из них.