You are given array a with n elements and the number m. Consider some subsequence of a and the value of least common multiple (LCM) of its elements. Denote LCM as l. Find any longest subsequence of a with the value l ≤ m.

A subsequence of a is an array we can get by erasing some elements of a. It is allowed to erase zero or all elements.

The LCM of an empty array equals 1.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^6) — the size of the array a and the parameter from the problem statement.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the elements of a.


-----Output-----

In the first line print two integers l and k_{max} (1 ≤ l ≤ m, 0 ≤ k_{max} ≤ n) — the value of LCM and the number of elements in optimal subsequence.

In the second line print k_{max} integers — the positions of the elements from the optimal subsequence in the ascending order.

Note that you can find and print any subsequence with the maximum length.


-----Examples-----
Input
7 8
6 2 9 2 7 2 3

Output
6 5
1 2 4 6 7

Input
6 4
2 2 2 3 3 3

Output
2 3
1 2 3

Difficulty: HARD
Tags: Number theory

Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
def main():
	from collections import Counter
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	m += 1
	tmp = Counter((x for x in l if 1 < x < m))
	num = [0] * m
	for (x, v) in list(tmp.items()):
		for i in range(x, m, x):
			num[i] += v
	lcm = max(list(range(m)), key=num.__getitem__)
	if lcm:
		tmp = {x for x in list(tmp.keys()) if not lcm % x}
		tmp.add(1)
		res = [i for (i, x) in enumerate(l, 1) if x in tmp]
	else:
		(res, lcm) = ([i for (i, x) in enumerate(l, 1) if x == 1], 1)
	print(lcm, len(res))
	if res:
		print(' '.join(map(str, res)))

def __starting_point():
	main()
__starting_point()


from sys import stdin
input = stdin.buffer.readline
(n, m) = map(int, input().split())
cnt = [0] * (m + 1)
(*b,) = map(int, input().split())
for i in b:
	if i <= m:
		cnt[i] += 1
a = [0] * (m + 1)
for i in range(1, m + 1):
	for j in range(i, m + 1, i):
		a[j] += cnt[i]
mx = idx = 0
for i in range(1, m + 1):
	if mx < a[i]:
		(mx, idx) = (a[i], i)
if mx == 0:
	exit(print(1, 0))
print(idx, mx)
for i in range(n):
	if idx % b[i] == 0:
		print(i + 1)


import sys
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
dp = [0] * (m + 1)
for x in a:
	if x <= m:
		dp[x] += 1
for i in range(m, 0, -1):
	for j in range(2, m + 1):
		if i * j > m:
			break
		dp[i * j] += dp[i]
lcm = max(1, dp.index(max(dp)))
ans = [i for (i, x) in enumerate(a, start=1) if lcm % x == 0]
sys.stdout.buffer.write((str(lcm) + ' ' + str(len(ans)) + '\n' + ' '.join(map(str, ans))).encode('utf-8'))


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
(n, m) = map(int, input().split())
cnt = [0] * (m + 1)
(*b,) = map(int, input().split())
for i in b:
	if i <= m:
		cnt[i] += 1
a = [0] * (m + 1)
for i in range(1, m + 1):
	for j in range(i, m + 1, i):
		a[j] += cnt[i]
mx = idx = 0
for i in range(1, m + 1):
	if mx < a[i]:
		(mx, idx) = (a[i], i)
if mx == 0:
	exit(print(1, 0))
print(idx, mx)
for i in range(n):
	if idx % b[i] == 0:
		print(i + 1)


import sys
(n, m) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
(B, C) = ([0] * (m + 1), [0] * (m + 1))
for a in A:
	if a <= m:
		B[a] += 1
for i in range(2, m + 1):
	for j in range(i, m + 1, i):
		C[j] += B[i]
(k, l) = (1, 0)
for i in range(2, m + 1):
	if C[i] > l:
		l = C[i]
		k = i
print(k, l + B[1])
for (i, a) in enumerate(A):
	if k % a == 0:
		sys.stdout.write(str(i + 1) + ' ')