В Берляндии проходят выборы. На выборах участвуют \(n\) кандидатов, пронумерованных от \(1\) до \(n\). У \(i\)-го из них есть \(a_i\) фанатов, которые проголосуют за него. Также дополнительно есть \(c\) людей, которые не определились с любимым кандидатом, назовем их неопределившимися. Неопределившиеся люди проголосуют за кандидата с наименьшим номером.
На выборах побеждает кандидат, который набрал максимальное количество голосов, а если максимальное количество голосов набрали несколько кандидатов, то среди таких побеждает кандидат с наименьшим номером.
Такие выборы вам показались слишком скучными и предсказуемыми, поэтому вы решили не допустить некоторых кандидатов к ним. Если вы не допустите кандидата с номером \(i\) к выборам, то все \(a_i\) его фанатов станут неопределившимися, и на выборах проголосуют за допущенного кандидата с наименьшим номером.
Вам стало интересно узнать для каждого \(i\) от \(1\) до \(n\), какое минимальное количество кандидатов надо не допустить к выборам, чтобы кандидат с номером \(i\) выиграл выборы.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел, \(i\)-е из которых должно быть равно минимальному количеству кандидатов, которых нужно не допустить к выборам, чтобы кандидат с номером \(i\) победил.
Примечание
В первом наборе входных данных:
- Если допустить всех кандидатов, то кандидат с номером \(1\) наберёт \(3\) голоса (за него проголосует \(1\) неопределившийся человек), кандидат с номером \(2\) наберёт \(0\) голосов, кандидат с номером \(3\) наберёт \(3\) голоса. Таким образом, выиграет кандидат с номером \(1\) (он набрал столько же голосов, сколько кандидат \(3\), но его номер меньше), поэтому для него ответ равен \(0\).
- Если не допустить кандидата с номером \(1\), то его \(2\) фаната станут неопределившимися. Тогда кандидат с номером \(2\) наберёт \(3\) голоса (за него проголосуют \(3\) неопределившихся человека) и кандидат с номером \(3\) наберёт \(3\) голоса. Таким образом, выиграет кандидат с номером \(2\) (он набрал столько же голосов, сколько кандидат \(3\), но его номер меньше), поэтому для него ответ равен \(1\).
- Если не допустить кандидатов с номерами \(1\) и \(2\), то выиграет кандидат с номером \(3\), поэтому для него ответ равен \(2\).
Во втором наборе входных данных кандидат с номером \(1\) выиграет, если не допустить кандидата с номером \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 1
2 0 3
2 3
0 10
5 3
5 4 3 2 1
4 5
3 10 7 1
6 0
2 2 2 3 3 3
|
0 1 2
1 0
0 1 2 3 4
1 0 2 3
1 1 2 0 4 5
|