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$