21574번 - Праздничный ужин 스페셜 저지다국어

Рядом с офисом компании, в которой работает программист Джон, открылось новое кафе. Директор компании решил провести там новогодний ужин. 

Меню праздничного новогоднего ужина в кафе состоит из k типов блюд. Для каждого типа блюда есть несколько вариантов на выбор. Всего есть a₁ вариантов для первого типа блюда, a₂ вариантов для второго типа блюда, и так далее, a_k вариантов для k-го типа блюда. Всего, таким образом, предлагается a₁×a₂×…×a_k различных заказов праздничного ужина.

Всего на ужине будут присутствовать m сотрудников компании. Каждый сотрудник должен заказать ровно один вариант блюда на выбор. Таким образом, ужин каждого сотрудника будет состоять из k блюд. Для того чтобы ужин каждого сотрудника компании был уникален, администратор кафе придумал следующую схему. Сотрудники делают заказ ужина по меню один за другим. Каждый сотрудник выбирает k блюд, по одному варианту каждого типа. После выбора варианта заказа из меню, сотрудник указывает на одно из заказанных им блюд, и этот вариант этого типа блюда больше не предлагается тем сотрудникам, которые делают заказ после него.

Каждый сотрудник компании запомнил, сколько возможных заказов ужина ему было предложено. Выяснилось, что директору, который выбирал первым, было предложено на выбор n₁ = a₁×a₂×…×a_k заказов. Тому, кто выбирал вторым, досталось лишь n₂ < n₁ заказов, поскольку один из вариантов одного из типов блюд уже не был доступен, и так далее. Джону, который выбирал последним, был предложен выбор лишь из n_m заказов. Джон заинтересовался, а какое количество вариантов каждого типа блюд было на выбор у директора компании.

Требуется написать программу, которая по заданным числам k, m и n₁, n₂, …, n_m выяснит, какое количество вариантов каждого типа блюд изначально предлагалось на выбор.

Первая строка входного файла содержит два целых числа k и m, разделенных ровно одним пробелом (1 ≤ k ≤ 20, 2 ≤ m ≤ 100). Вторая строка содержит m чисел: n₁, n₂, …, n_m (для всех i от 1 до m выполняется неравенство 1 ≤ n_i ≤ 10⁹).

Выходной файл должен содержать k чисел: a₁, a₂, …, a_k. Если возможных вариантов решения поставленной задачи несколько, требуется вывести любой. Соседние числа должны быть разделены ровно одним пробелом. Гарантируется, что хотя бы одно решение существует.

События в примере могли развиваться, например, следующим образом. 

Исходно было 3×2×2=12 вариантов заказа ужина. Директор, выбрав один из вариантов, указал на свое первое блюдо, поэтому второму сотруднику предлагалось уже лишь 2 варианта первого блюда. У него осталось 2×2×2 = 8 вариантов ужина. Он также указал на свое первое блюдо, и Джон уже мог выбирать лишь из 1×2×2 = 4 вариантов ужина.