Незваные гости

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

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

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

К сожалению, Морти опять нажал не на тот переключатель на стене, и в системе логирования все сбилось --- она все еще исправно делает записи, однако эти записи могут быть перепутаны и следовать в произвольном порядке.

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

В первой строке ввода через пробел даны два целых числе $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$-й категорией опасности.

Во второй строке в том же формате выведите максимально возможные количества посетителей каждой категории.