Sunny founded a software startup with $N$ programmers. To reduce the number of bugs the programmers create, Sunny's startup is adopting pair programming. Each programmer will be assigned a partner to write code together. You are not allowed to do this in today's contest.

We may assume that if both partners are at the office, they will always engage in pair programming. However, programmers at Sunny's startup can choose to work from home. It may be the case that one or both of programmers are working remotely, in which case they cannot perform pair programming.

Initially, all programmer work at the office. However, any of them may change their mind at any time: switching from working in the office to working from home and vice versa. Whenever a programmer changes their mind, you should count the number of pairs of partners that can perform pair programming at the office.

Input

The first line of input contains two integers $N$ and $Q$.
Each of the next $\frac{N}{2}$ lines of input contains two names. They are two programmers assigned as partners. The $N$ names are guaranteed to be unique and consist of at most 10 lowercase English letters.
Each of the next $Q$ lines of input contains the name of a programmer. It means that this programmer is changing their mind: if they are working at the office, they now switch to working from home; if they are working from home, they now switch to working at the office.

Output

Output $Q$ lines. On the $i$-th line, output the number of pairs of partners that can perform pair programming at the office after the first $i$ changes.

Constraints

$N$ is even.
Subtask 1 (40%): $1 \le N, Q \le 10^3$
Subtask 2 (60%): $1 \le N, Q \le 10^5$