Products both customers bought

Problem

Two customers each have a list of the products they bought; a product can appear several times. Find the products that both customers bought. For each, print the total number of times the two customers bought it together. Print the products in alphabetical order.

Input, output and limits

Input: The first line has n1, then a line with n1 product names. Then a line with n2, then a line with n2 product names.
Output: One line <product> <total> for each product bought by both, sorted by name, or NONE if there is no such product.
Constraints: 1 ≤ n1, n2 ≤ 100000
Names have 1 to 20 lowercase letters

Examples

Example

Input

5
pen mouse pen cable pen
4
mouse pen laptop mouse

Output

mouse 3
pen 4

mouse: 1 + 2 = 3 times; pen: 3 + 1 = 4 times. cable and laptop are bought by one customer only.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Count the first list in one map and the second list in another map.

Hint 2

Loop over one map and check containsKey on the other.

Hint 3

A TreeMap for the first map makes the loop run in A-Z order.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Maps problems

Problem

Input, output and limits

Examples

Hints

More Maps problems