A space station has D named habitat modules and a roster of S crew members. Each crew member is either assigned to exactly one module (identified by that module's 1-indexed position in the module list) or is currently unassigned (marked with module id 0, meaning a visiting crew member who belongs to no module and should not be counted anywhere). Station command wants a census: for every module, how many crew members currently live in it -- including modules that happen to have zero crew. Report the modules ordered from busiest to least busy, breaking any tie in crew count by the module's name in ascending alphabetical order.

Input format

Line 1 contains two space-separated integers D and S: the number of modules and the number of crew members. The next D tokens are the module names, in order -- module i (1-indexed) is named by the i-th of these tokens. Names consist only of letters and digits, contain no spaces, and are pairwise distinct. The next S tokens are integers a[1], ..., a[S], one per crew member, where a[k] is the id of the module crew member k is assigned to (an integer in [1, D]), or 0 if that crew member is unassigned.

Output format

Print exactly D lines, one per module, each containing the module's name followed by a single space and its crew count. Order the lines by crew count descending; among modules with equal crew count, order by module name ascending.

Constraints

• 1 <= D <= 1000
• 0 <= S <= 10^5
• Each module name has length between 1 and 20 and matches [A-Za-z0-9]+.
• Each a[k] is an integer in [0, D].

3 5
Hydroponics Command Reactor
1 2 1 0 3

Hydroponics 2
Command 1
Reactor 1

2 0
Alpha Beta

Alpha 0
Beta 0