The newly launched SH Weibo has $n$ users (labeled $1 \dots n$). Within this short month, users have been active, with $m$ records in chronological order:

• ! x indicates that user $x$ posted a Weibo message;
• + x y indicates that user $x$ and user $y$ became friends;
• - x y indicates that user $x$ and user $y$ ended their friendship.

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

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

After these $m$ records have occurred, calculate how many messages each user has seen.

Input

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

The next $m$ lines contain the $m$ records in chronological order. Each record is formatted as described in the problem, with values separated by spaces.

Output

Output a single line containing $n$ space-separated integers (with no trailing space), where the $i$-th integer represents the number of messages user $i$ has seen.

Examples

Input 1

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

Output 1

1 1

Note

Only the messages corresponding to the 4th and 5th records were seen. When the other messages were posted, 1 and 2 were not friends.

Constraints

Table 1. Constraints on n and m