Challenge: Shared Interests

Lab Java Intermediate 20 points

Two friends each list their hobbies (single words, a friend may repeat one). Print the hobbies they both have, each once, in alphabetical order. Print nothing in common if there are none.

Input

Line 1: n then n words. Line 2: m then m words.

Output

The shared hobbies separated by spaces, or nothing in common.

Example

Input

4 chess music hiking chess
3 music chess swimming

Output

chess music

Sample input available Sample output available

Editor

Java

Hints

Put the first friend's hobbies in a HashSet.

For the second friend, keep matches in a TreeSet – it removes repeats and keeps a–z order.

Solution explanation

Building the set is O(n), checking each of the m words is O(1) each. The TreeSet gives the sorted, no-repeats answer for free. String.join glues the words with spaces.

Show solution

import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashSet<String> first = new HashSet<String>();
        for (int i = 0; i < n; i++) first.add(sc.next());
        int m = sc.nextInt();
        TreeSet<String> both = new TreeSet<String>();
        for (int i = 0; i < m; i++) {
            String w = sc.next();
            if (first.contains(w)) both.add(w);
        }
        if (both.isEmpty()) {
            System.out.println("nothing in common");
        } else {
            System.out.println(String.join(" ", both));
        }
    }
}

Output

Answer