Description

The newly launched SH Weibo has $n$ users (labeled $1\sim n$). During this brief month, users were very active, and there are $m$ records in chronological order:

! x 表示用户 x 发了一条微博；
+ x y 表示用户 x 和用户 y 成为了好友
− x y 表示用户 x 和用户 y 解除了好友关系

When a user posts a Weibo, all of their friends (direct connections) will see the message.

Assume that initially no one is friends with anyone else, and all records are valid (i.e., when + x y occurs, $x$ and $y$ are not friends; when − x y occurs, $x$ and $y$ are friends).

After these $m$ records, determine how many messages each user has seen.

Input Format

The first line contains two integers $n$, $m$.

The next $m$ lines contain the records in chronological order, each formatted as described above and separated by spaces.

Output Format

Output one line with $n$ space-separated integers (no trailing space). The $i$-th number denotes the number of messages seen by user $i$.

2 8
! 1
! 2
+ 1 2
! 1
! 2
- 1 2
! 1
! 2

1 1

Hint

For $100\%$ of the testdata, $n \leq 200000$, $m \leq 500000$.

Translated by ChatGPT 5