// Note: This is a subset of java.util.Set
interface Set<E> extends Collection<E> {
    boolean add(E x);       // Adds x to the set. Returns true if the element wasn't already in the set.
    boolean remove(E x);    // Removes x from the set. Returns true if the element was in the set.
    boolean contains(E x);  // Returns true if x is in the set.
    // Note: iterator() can yield the elements in any order.
}

class SpellChecker {
    Set<String> set_of_valid_words;

    SpellChecker(String[] list_of_valid_words) {
        // Convert the list of words into a set.
        set_of_valid_words = new HashSet<>();
        for (String word : list_of_valid_words)
            set_of_valid_words.add(word);
    }

    public boolean is_valid_word(String word) {
        return set_of_valid_words.contains(word);
    }

    public static void main(String args[]) {
        // Create a new spell checker.
        SpellChecker checker = new SpellChecker(new String[]{"cat", "dog"});

        // Select some words to spell check. 
        // If there are no command-line arguments, default to testing "dog" and "kat".
        String[] list_of_words_to_check = args.length > 0 ? args : new String[]{"dog", "kat"};  

        // Now we can spell-check a word easily.
        for (String word : list_of_words_to_check) {
            if (checker.is_valid_word(word)) {
                System.out.println(word + " is valid");
            } else {
                System.out.println(word + " is INVALID");
            }
        }
    }
}

// Note: This is a subset of java.util.Map, where
// `iterator` iterates over the keys, and replaces the more complicated `keySet`.
interface Map<K, V> extends Iterable<K> {
    V put(K key, V value);       // Sets the value of the given key. Returns the previous value, or null.
    V get(K key);                // Returns the value associated with the given key, or null if the key is not there.
    V remove(K key);             // Removes and returns the value associated with the given key, or null if there is no key.
    boolean containsKey(K key);  // Returns true if the key has an associated value.
    boolean isEmpty();           // Returns true if there are no keys.
    int size();                  // Returns the number of keys (i.e., the number of key/value pairs).
    // Note: iterator() can yield the keys in any order.
}

class Person {
    public String pnr;    // personnummer
    public String name;   // person's name

    Person(String pnr, String name) {
        this.pnr = pnr;
        this.name = name;
    }
}

class PersonDatabase {
    Map<String, Person> database;
    PersonDatabase() {
        database = new HashMap<>();
    }

    // Put the person in the database.
    public void put(Person p) {
        database.put(p.pnr, p);
    }

    // Remove a person from the database.
    public void remove(Person p) {
        database.remove(p.pnr);
    }

    // Find the person who has a given personnummer.
    public Person find(String pnr) {
        return database.get(pnr);
    }
}

// We model a document as a list of words.
class Document {
    public String[] contents;
    Document(String[] contents) {
        this.contents = contents;
    }
}

class SearchEngine {
    Map<String, Set<Document>> database;
    SearchEngine() {
        database = new HashMap<>();
    }

    // Add a new document to the database.
    public void add(Document doc) {
        for (String word : doc.contents) {
            // Get the set of documents containing this word.
            Set<Document> set = database.get(word);
            if (set == null) 
                // This is the first document containing this word.
                set = new HashSet<>();

            // Add the document to the set.
            set.add(doc);
            database.put(word, set);
        }
    }

    // Find all documents containing a given word.
    public Set<Document> find(String word) {
        if (database.containsKey(word))
            return database.get(word);
        else
            // If the word is not found, return an empty set rather than null.
            return new HashSet<>();
    }
}

// Note: This is a subset of java.util.SortedMap, where
// `floorKey` and `ceilingKey` are borrowed from java.util.NavigableMap.
interface SortedMap<K, V> extends Map<K, V> {
    K firstKey();                         // Returns the first (smallest) key. Raises an exception if the map is empty.
    K lastKey();                          // Returns the last (largest) key. Raises an exception if the map is empty.
    K floorKey(K key);                    // Returns the closest key <= k, or null if there is no key.
    K ceilingKey(K key);                  // Returns the closest key >= k, or null if there is no key.
    K lowerKey(K k);                      // Returns the closest key < k, or null if there is no such element.
    K higherKey(K k);                     // Returns the closest key > k, or null if there is no such element.
    Iterator<K> keysBetween(K k1, K k2);  // Returns all keys such that k1 <= k <= k2.
    // Note: iterator() should yield the keys in order.
}

// Note: This is a subset of java.util.SortedSet, where
// `floor` and `ceiling` are borrowed from java.util.NavigableSet.
interface SortedSet<E> extends Set<E> {
    E first();                        // Returns the first (smallest) element. Raises an exception if the set is empty.
    E last();                         // Returns the last (largest) element. Raises an exception if the set is empty.
    E floor(E x);                     // Returns the closest element <= x, or null if there is no such element.
    E ceiling(E x);                   // Returns the closest element >= x, or null if there is no such element.
    E lower(E x);                     // Returns the closest element < x, or null if there is no such element.
    E higher(E x);                    // Returns the closest element > x, or null if there is no such element.
    Iterator<E> between(E x1, E x2);  // Returns all elements x such that x1 <= x <= x2.
    // Note: iterator() should yield the elements in order.
}

class City {
    public String name;
    public Integer population;
    City(String name, Integer population) {
        this.name = name;
        this.population = population;
    }
}

class CityPopulations {
    // Similar to the search engine, use a map where the value is a list of cities.
    SortedTreeMap<Integer, Set<City>> cities;
    CityPopulations() {
        cities = new SortedTreeMap<>();
    }

    // Add a new city to the database.
    public void add(City city) {
        // Get the set of documents containing this city.
        Set<City> set = cities.get(city.population);
        if (set == null)
            // This is the first city with this population
            set = new HashSet<>();

        // Add the city to the set
        set.add(city);
        cities.put(city.population, set);
    }

    // Find all cities with a population between lower and upper.
    public Set<City> findBetween(Integer lower, Integer upper) {
        Set<City> result = new HashSet<>();
        // The range query returns a set of keys, i.e. populations.
        Iterator<Integer> it = cities.keysBetween(lower, upper);
        while (it.hasNext()) {
            Integer population = it.next();
            // cities.get(population) returns the list of cities with that population.
            for (City city : cities.get(population))
                result.add(city);
        }
        return result;
    }
}