Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#00062B

NZD - Okružno 2012

An array a of n positive integers is given to you. In one move you can choose any two adjacent elements and replace them with their sum. For example, if we choose elements ai and ai + 1, the array (a1, a2, ..., ai, ai + 1, ... an) will become (a1, a2, ..., ai + ai + 1, ... an). This action can then be repeated on newly formed arrays (Notice that the number of elements decreases by 1 after every move).


Your task is to apply a number of moves to this array, so that in the end you have exactly k numbers remaining with the greatest possible common divisor.


InputIn the first line of input there are 2 integers n and k which represent the number of elements in the original array and the number of elements which should remain in the array at the end, respectively (1 ≤ k < n ≤ 100,000). The next line contains n positive integers ai which represent the original array (ai ≤ 1,000,000). The sum of all elements will not exceed 1,000,000.

OutputIn the first line write the greatest possible common divisor of all remaining numbers. In the second line you should write k positive integers - the array after all the moves have been executed. If there are many solutions, you can write any one of them.

Sample input:
6 3
12 7 3 2 15 15
Sample output:
6
12 12 30

Explanation:


If we execute the following moves (12, 7, 3, 2, 15, 15) → (12, 10, 2, 15, 15) → (12, 10, 2, 30) → (12, 12, 30) we get numbers 12, 12 i 30 whose greatest common divisor is 6. It is impossible to get 3 numbers with a larger greatest common divisor.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.