Counting Multiples

We are given an integer \(n\), a positive integer \(m\), and an array \(a\) of \(n\) positive integers. For every integer \(k\) such that \(0 \le k \le n\), compute the number of integers \(x\) in the range \([1, m]\) such that exactly \(k\) elements of \(a\) divide \(x\). In other words, there exists exactly \(k\) indices \(i\) (with \(1 \le i \le n\)) for which \(a_i \mid x\).

The array elements \(a_i\) are positive integers generated uniformly at random in the range \([1, 10^9]\).

Note: It is guaranteed that \(n\) is small enough to allow a solution that iterates over all subsets of \(a\) (for example, \(n \le 15\)).

inputFormat

The first line contains two positive integers \(n\) and \(m\) separated by a space.

The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output \(n+1\) integers separated by spaces, where the \(k^{th}\) number (starting from \(k=0\)) is the count of integers \(x\) in \([1, m]\) that are divisible by exactly \(k\) elements of the array \(a\).

sample

2 10
2 3

3 6 1