Императивные языки программирования позволяют использовать как линейные, так и многомерные массивы. Например, в языке Паскаль для массива с именем X выражение array[0..2, 0..1, 0..3] объявляет трёхмерный массив со следующими ограничениями для каждой размерности: 0..2, 0..1, 0..3. (В этой задаче мы будем рассматривать только массивы, каждая размерность которых начинается с нуля, хотя в Паскале возможны и другие значения нижних границ размерностей.)

Можно определить порядок, в котором перечислены элементы массива. Этот порядок определяется принципом "чем правее индекс, тем быстрее он меняется". Это значит, что последний (самый правый) индекс проходит по всем возможным значениям, затем соседний с ним индекс (второй справа) меняет своё значение на 1, а последний индекс опять проходит по всем значениям между нижней и верхней границей, и так далее.

Пример. Элементы упомянутого выше массива перечисляются в следующем порядке: X[0,0,0], X[0,0,1], X[0,0,2], X[0,0,3], X[0,1,0], X[0,1,1], X[0,1,2], X[0,1,3], X[1,0,0], X[1,0,1], X[1,0,2], X[1,0,3], X[1,1,0], X[1,1,1], X[1,1,2], X[1,1,3], X[2,0,0], X[2,0,1], X[2,0,2], X[2,0,3], X[2,1,0], X[2,1,1], X[2,1,2], X[2,1,3].

Пусть n-мерный массив X описан как array[0..k₁, 0..k₂, …, 0..k_n]. Теория говорит, что порядковый номер P любого элемента X[i₁, i₂, …, i_n] находится как P(i₁, i₂, …, i_n) = 1 + D₁*i₁ + D₂*i₂ + … + D_n*i_n, если используется порядок перечисления элементов, описанный выше. Здесь D₁, D₂, …, D_n — так называемые множители индексов.

Пример. Для рассматриваемого массива множители индексов равны D₁ = 8, D₂ = 4, D₃ = 1. Поэтому, например, порядковый номер элемента X[1,0,3] будет равен P(1,0,3) = 1+8*1+4*0+1*3 = 12.

Ваша задача — найти неизвестные верхние границы размерностей массива (k₁, k₂, …, k_n) по заданным множителям индексов D₁, D₂, …, D_n, и общему количеству элементов, содержащихся в массиве.

Первая строка ввода содержит n — количество размерностей (1 ≤ n ≤ 20) и s — общее количество элементов массива (1 ≤ s < 2³¹−1). Следующие n строк содержат множители индексов D₁, D₂, …, D_n.

Найдите верхние границы для каждой размерности массива в порядке: k₁, k₂, …, k_n (0 < k_i ≤ 1000). Числа должны быть разделены пробелами и/или переводами строк.