Background

Special for beginners, ^_^

Description

最近信奥数学选课人数太少，徐老师忧心忡忡，毕竟信奥界有句名言，C++决定下界，数学决定上界。他决定让家长通过手机通讯录群发短信的方式给信奥数学打打广告，领取信奥数学题单并刷了它。

假设徐老师一共通知了n（<=1e6）名用户。为了简单起见，假设所有用户一开始的手机通讯录是空的。如此假设没有问题，因为可以在某用户群发短信前先把手机通讯录的好友添加情况放上。

接下来有 m （<=1e6）条关于用户的操作记录：

第一种记录形式为 + x y，表示两名用户 x 与 y 手机通讯录互相添加；

第二种记录形式为 - x y，表示两名用户 x 与 y 手机通讯录互相删除；

第三种记录形式为 ! x，表示用户x往手机通讯录里面的所有好友群发了一条领取信奥数学的题单的短信。

经过这些操作之后，请统计并输出每一名用户收到了多少条短信。

Format

Input

第一行：两个整数 n 与 m；

接下来 m 行：每行表示一条操作记录，格式如题面所述。为了化简问题，特别保证：

互加通讯录时，一定没有对方。

互删通讯录时，一定有对方。

也就是说，不存在冗余或者无效的记录。

Output

单独一行：n 个整数，分别表示 n 名用户收到的照片数量。

Samples

3 5
+ 1 2
! 1
- 1 2
! 1
! 3

0 1 0

Limitation

1s, 1024KiB for each test case.