Алиса и Боб играют в игру. Игра состоит из нескольких сетов, и каждый сет состоит из нескольких раундов. Каждый раунд выиграл либо Боб, либо Алиса, и сет считается завершенным, когда один из игроков выиграл \(x\) раундов подряд. Например, если Боб выиграл пять раундов подряд и \(x = 2\), то завершилось два сета.
Вы знаете, что Алиса и Боб уже сыграли \(n\) раундов и вы знаете результаты нескольких раундов. Для каждого \(x\) от \(1\) до \(n\), посчитайте максимальное количество сетов, которое могло быть завершено, если сет считается завершенным, когда один из игроков выиграл \(x\) раундов подряд. Если последний сет не завершен — то учитывать его не нужно.
Выходные данные
В единственной строке выведите \(n\) чисел. \(i\)-е должно быть равно максимальному количество сетов, которое могло быть завершено, если сет считается завершенным когда один из игроков выиграл \(i\) раундов подряд.
Примечание
Рассмотрим первый набор входных данных:
- если \(x = 1\) и \(s = 110000\) или \(s = 111000\) то есть шесть завершенных сетов;
- если \(x = 2\) и \(s = 110000\) то есть три завершенных сета;
- если \(x = 3\) и \(s = 111000\) то есть два завершенных сета;
- если \(x = 4\) и \(s = 110000\) то есть один завершенный сет;
- если \(x = 5\) то завершенных сетов нет;
- если \(x = 6\) то завершенных сетов нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
11?000
|
6 3 2 1 0 0
|
|
2
|
5
01?01
|
5 1 0 0 0
|
|
3
|
12
???1??????1?
|
12 6 4 3 2 2 1 1 1 1 1 1
|