410171: GYM103967 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 -

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

1 1 
2 1 

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

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

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

1 1 1 
2 2 1