410163: GYM103966 G Незваные гости

G. Незваные гостиограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рик решил, что пока он работает над довольно серьезным изобретением в своей новой лаборатории, он хочет знать, кто за это время посещает Землю, ведь среди таких посетителей могут оказаться как люди из Галактической Федерации, так и более опасные личности.

Для этого Рик классифицировал всех возможных существ во Вселенной и разбил их на $$$n$$$ групп по степени их опасности или подозрительности.

Система логирования устроена довольно просто, и в тот момент, когда кто-то с категорией опасности $$$i$$$ прилетает за Землю, она делает запись ($$$i$$$ +), а когда кто-то с такой категорией опасности покидает планету — делает запись ($$$i$$$ -). Известно, что в момент запуска системы на планете находятся только люди, которых Рик вообще не воспринимает как угрозу, и поэтому не отнес ни к одной категории.

В какой-то момент Рик посмотрел на логи, в которых уже накопилось $$$m$$$ записей, и обеспокоился тем, что из некоторых подозрительных категорий планету посещало достаточно много личностей. По записям в логах помогите Рику определить минимально возможное число различных людей существ из каждой категории, которые посещали Землю. Разумеется, никто не может прилететь на Землю два раза подряд, предварительно не улетев перед этим.

Входные данные

В первой строке ввода через пробел даны два целых числе $$$n$$$ и $$$m$$$ — количество категорий существ и количество записей в логах ($$$1 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant m \leqslant 3 \cdot 10^5$$$).

В следующих $$$m$$$ строках даны записи логирующей системы. В одной записи содержится число $$$x_i$$$ и символ '+' — кто-то из $$$x_i$$$-й категории прилетел на Землю, или '-' — кто-то покинул планету ($$$1 \leqslant x_i \leqslant n$$$).

Выходные данные

Выведите в одной строке $$$n$$$ целых чисел через пробел, $$$i$$$-е число должно быть равно минимально возможному количеству различных посетителей с $$$i$$$-й категорией опасности.

ПримерыВходные данные

2 4
1 +
1 +
2 +
1 -

Выходные данные

2 1 

Входные данные

3 10
1 +
1 +
2 +
2 -
1 -
2 +
3 +
3 -
1 -
2 -

Выходные данные

2 1 1