У вас есть массив \(a\) размера \(n\), изначально заполненный нулями (\(a_1 = a_2 = \ldots = a_n = 0\)). Также у вас есть массив целых чисел \(c\) размера \(n\).
Изначально у вас есть \(k\) монет. Заплатив \(c_i\) монет, вы можете прибавить \(1\) ко всем элементам массива \(a\) с первого по \(i\)-й (\(a_j \mathrel{+}= 1\) для всех \(1 \leq j \leq i\)). Покупать любое \(c_i\) можно произвольное число раз. Покупка возможна только при \(k \geq c_i\), то есть в любой момент должно выполняться \(k \geq 0\).
Найдите лексикографически наибольший массив \(a\), который возможно получить.
Массив \(a\) лексикографически меньше массива \(b\) такой же длины, если и только если в первой позиции, где \(a\) и \(b\) различны, в массиве \(a\) элемент меньше, чем соответствующий элемент в \(b\).
Выходные данные
На каждый набор входных данных выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — лексикографически наибольший массив \(a\), который можно получить.
Примечание
В первом наборе входных данных \(a_1\) не может быть больше \(5\), а если пять раз купить \(c_1\), то у нас не останется денег, поэтому \(a = [5, 0, 0]\).
Во втором наборе входных данных \(a_1\) не может быть больше \(2\), при этом мы можем купить \(c_1\) и \(c_2\) по одному разу (купить \(c_2\) дважды не получится), поэтому \(a = [2, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2 3
5
2
3 4
7
3
3 2 1
2
6
10 6 4 6 3 4
7
|
5 0 0
2 1
2 2 2
2 2 2 2 2 1
|