Omar loves problem solving very much and today he faces the following problem.

Given a multiset A of N integers \({a_1, a_2, \ldots, a_N}\) and an integer L, his task is to perform L operations indexed from 1 to L in the ascending order of their indices.

Let's consider the operation with index i. Moreover, for \(i > 1\), let \(p_{max}\) be a prime number in prime factorization of i with the greatest exponent in the factorization. If there are multiple primes with the greatest exponent in prime factorization of i, let \(p_{max}\) be the smallest one among them. The operation with index i is beneficial if and only if \(i = 1\) or the remainder of division \(p_{max}\) by i is odd. Otherwise the operation is harmful.

For example, operation with index \(i = 2\) is harmful, because \(p_{max} \bmod i = 2 \bmod 2 = 0\) which is even. On the other hand, operation with index \(i = 9\) is beneficial, because \(p_{max} \bmod i = 3 \bmod 9 = 3\) which is odd.

Omar must perform all L operations in ascending order of their indices. For each beneficial operation, he has to choose an integer from A and double its value. On the other hand, for each harmful operation, he has to choose an integer from A and divide its value by 2 using integer division. If during any operation any element of A becomes 0, then he removes this element from A. In addition, once A becomes empty, it is not affected by any future operations. In order for the problem to be a challenging one, the task is to maximize the sum of elements in A after performing all the operations.

Since Omar is not familiar with any math, he asks you for help in solving the problem.

Input:

In the first line of the input there are two space separated integers N and L denoting the size of the multiset A and the number of operations to perform. In the second line, there are N space separated integers denoting the elements of A.

Output:

In the first line, print a single integer K denoting the size of multiset A after all operations are performed. In the second line, print exactly K space separated integers denoting the elements of A after all operations are performed. Print them in the non-decreasing order of their values. Since these values can be very large, print each value taken modulo \(10^9+7\) (Notice that this modulo operation is applied when the order of these elements is determined and it does not affect this order).

Constraints:

\(1 \le N, L \le 5 \cdot 10 ^ 5\)
\(1 \le a_i \le 10 ^ 6\)