This page is still under construction.

Parts of this page are still being built. What you see may change.

Gahui and Keywords

Time limit1.5sMemory limit512 MB

Summary
Keep a set of notebook keywords, remove the keywords named in each comma-separated post line, and report the remaining count after each post.
Level

Medium4 of 10

Topics
Hash map, String, Implementation, Simulation
Solved
No attempts yet

Problem

Gahui runs a blog. To write posts for the blog, Gahui writes keywords down in a notebook.

The keywords written in the notebook so far are all distinct, and there are N of them in total.

When Gahui writes a new post, she writes about at most 10 keywords.

Any of these keywords that was in the notebook is erased from the notebook after Gahui writes the post.

After writing a post on the blog, Gahui wants to know how many keywords are in the notebook. Help Gahui.

Input

The first line gives the number of keywords Gahui wrote in the notebook, N, and the number of posts Gahui wrote on the blog, M, separated by a space.

Lines 2 through N+1 give the N keywords written in the notebook.

Lines N+2 through N+M+1 give the keywords related to the post Gahui wrote, separated by , (commas). Note that they are not separated by spaces.

Output

On line x, print the number of keywords remaining in the notebook after the x-th post is written.

Constraints

  • 1 ≤ N ≤ 2×105
  • 1 ≤ M ≤ 2×105
  • 1 ≤ number of keywords in a post ≤ 10
  • 1 ≤ keyword length ≤ 10
  • Keywords consist only of lowercase letters and digits.
  • Keyword names in the notebook are distinct.
  • Keyword names in a post are distinct. However, one keyword may appear in multiple posts.

Examples2

  1. Example 1

    Input
    5 2
map
set
dijkstra
floyd
os
map,dijkstra
map,floyd
    Expected output
    3
2

  2. Example 2

    Input
    2 2
gt26cw
1211train
kiwoom,lottegiant
kbo
    Expected output
    2
2