SH Weibo Activity

Recently, SH Weibo was launched with \(n\) users (numbered from 1 to \(n\)). During the first month, the users were very active, and there were \(m\) records of events, listed in chronological order.

The records come in three types:

• ! x: User \(x\) posts a weibo. Every friend of \(x\) (i.e. users who have a direct friendship relation with \(x\)) will see the post.
• + x y: Users \(x\) and \(y\) become friends. It is guaranteed that they were not friends before this record.
• - x y: Users \(x\) and \(y\) cease being friends. It is guaranteed that they were friends before this record.

Initially, no users are friends with each other. After processing the \(m\) records sequentially, determine for each user the total number of weibos they have seen.

Note: When a user posts a weibo, the post is seen only by the friends at that moment; earlier posts are not retroactively seen by friends formed later.

inputFormat

The first line contains two integers \(n\) and \(m\) --- the number of users and the number of records.

The next \(m\) lines each contain a record in one of the following formats:

• ! x
• + x y
• - x y

It is guaranteed that all records are valid.

outputFormat

Output \(n\) integers separated by spaces. The \(i\)th integer represents the total number of weibos that the user with id \(i\) has seen.

sample

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

1 2 1