Рик решил, что пока он работает над довольно серьезным изобретением в своей новой лаборатории, он хочет знать, кто за это время посещает Землю, ведь среди таких посетителей могут оказаться как люди из Галактической Федерации, так и более опасные личности.
Для этого Рик классифицировал всех возможных существ во Вселенной и разбил их на $$$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