В компьютерной игре есть \(n\) героев. У каждого героя есть здоровье \(h\) и изначальная броня \(a\). Пусть текущее количество брони равно \(a_{\mathit{cur}}\), изначально равное \(a\).
Когда герою наносится \(x\) урона, происходит следующее: если \(x < a_{\mathit{cur}}\), то из \(a_{\mathit{cur}}\) вычитается \(x\); иначе из \(h\) вычитается \(1\), а \(a_{\mathit{cur}}\) снова становится равно \(a\).
В начале игры вы выбираете значение \(x\) (целое число, строго большее \(0\)). Затем вы атакуете героев, пока все не погибнут: за один раунд вы наносите \(x\) урона каждому живому герою. Герой погибает, когда его здоровье становится равно \(0\). Игра заканчивается, когда все герои погибают.
Последний погибший герой получает количество очков, равное количеству раундов, в течение которых он был единственным живым героем. Остальные герои получают \(0\) очков. В частности, если в последнем раунде погибают несколько героев, то все герои получают \(0\) очков.
Вы сыграли по одной игре на каждое возможное значение \(x\) (от \(1\) до бесконечности). Между играми очки сбрасывались. Какое наибольшее количество очков было у каждого героя?
Выходные данные
На каждый набор входных данных выведите \(n\) целых чисел — максимальное количество очков, которое было у героя в течение игр, сыгранных для каждого возможного \(x\).
Примечание
В первом наборе входных данных игра на \(x = 1\) играется так:
- до всех раундов: у героев \(h = [3, 1, 2]\), \(a_{\mathit{cur}} = [3, 11, 5]\);
- раунд \(1\): \(1\) урона наносится всем героям: \(h\) остается \([3, 1, 2]\), \(a_{\mathit{cur}}\) становится \([2, 10, 4]\);
- раунд \(2\): \(h = [3, 1, 2]\), \(a_{\mathit{cur}} = [1, 9, 3]\);
- раунд \(3\): у первого героя заканчивается броня, поэтому он теряет очко здоровья: \(h = [2, 1, 2]\), \(a_{\mathit{cur}} = [3, 8, 2]\);
- ...
- раунд \(9\): первый герой погибает, так как его здоровье становится равно \(0\): \(h = [0, 1, 1]\), \(a_{\mathit{cur}} = [0, 2, 1]\);
- раунд \(10\): третий герой погибает: \(h = [0, 1, 0]\), \(a_{\mathit{cur}} = [0, 1, 0]\);
- раунд \(11\): второй герой погибает: \(h = [0, 0, 0]\), \(a_{\mathit{cur}} = [0, 0, 0]\).
Второй герой погиб последним, и был единственным живым героев в течение одного раунда. Поэтому он получает \(1\) очко за эту игру.
Игра на \(x = 4\) играется так:
- раунд \(1\): \(h = [2, 1, 2]\), \(a_{\mathit{cur}} = [3, 7, 1]\);
- раунд \(2\): \(h = [1, 1, 1]\), \(a_{\mathit{cur}} = [3, 3, 5]\);
- раунд \(3\): \(h = [0, 0, 1]\), \(a_{\mathit{cur}} = [0, 0, 1]\);
- раунд \(4\): \(h = [0, 0, 0]\), \(a_{\mathit{cur}} = [0, 0, 0]\);
Третий герой погиб последним, и был единственным живым героев в течение одного раунда.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
3 1 2
3 11 5
1
100
200
4
5 9 5 1
9 2 9 10
|
1 1 1
20000
0 4 0 0
|