Пало-Алто — необычный город, ведь он представляет собой бесконечную координатную прямую. Он известен еще тем, что там находится офис Lyft Level 5.
Lyft стал настолько популярным, что его сейчас используют все \(m\) таксистов в городе, которые каждый день подвозят остальных жителей города — \(n\) пешеходов.
Каждый житель (включая таксистов) Пало-Алто живёт в точке с уникальной координатой (нет такой пары жителей, что их координата одинаковая).
Система Lyft очень умная: когда человек вызывает такси, то его вызов идет не ко всем таксистам, а только к тому, который является ближайшим к этому человеку, а если таких несколько, то к тому, у кого меньше текущая координата.
Однажды утром таксистам стало интересно: а сколько же есть людей, от которых они могут получить первый вызов в этот день? Другими словами, надо для каждого таксиста \(i\) найти число \(a_{i}\) — количество пешеходов, для которых \(i\)-й таксист — ближайший, или, если таких таксистов несколько, имеет среди таковых наименьшую координату.
Таксист не может подвезти самого себя или других таксистов.
Выходные данные
Выведите \(m\) чисел \(a_1, a_2, \ldots, a_{m}\), где \(a_i\) — ответ для \(i\)-го таксиста. Таксист имеет номер \(i\), если среди всех таксистов он живет в \(i\)-й по величине координате (смотрите примеры для лучшего понимания).
Примечание
В первом примере у нас всего один таксист, значит заказ от любого из \(n\) пешеходов будет идти к нему.
Во втором примере первый таксист живет в точке с координатой \(2\), а второй — с координатой \(6\). Очевидно, что ближайший таксист к пешеходу, который живет на координате \(3\) — это первый, а к пешеходу, который живет на координате \(5\) — это второй. Пешеход, который живет в координате \(4\), имеет одинаковое расстояние как до первого, так и до второго таксиста, но поскольку первый таксист имеет меньшую координату, вызов от данного пешехода будет идти к первому таксисту.
В третьем примере у нас один пешеход и ближайший к нему таксист — четвёртый.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1 2 3 10
0 0 1 0
|
3
|
|
2
|
3 2
2 3 4 5 6
1 0 0 0 1
|
2 1
|
|
3
|
1 4
2 4 6 10 15
1 1 1 1 0
|
0 0 0 1
|