import java.io.*;
import java.util.*;


class Trie {
    final TrieNode root;

    public Trie() {
        this.root = new TrieNode('#');
    }

    public int getRelevenceCountOfString(final String s) {
        TrieNode current = root;
        for (int i=0;i<s.length();i++) {
            if (current == null || current.next(s.charAt(i)) == null) {
                return 0;
            } else {
                current = current.next(s.charAt(i));
            }
        }
        return current.relevenceCount;
    }

    public void insert(final String s) {
        TrieNode current = root;
        for (int i=0;i<s.length();i++) {
            if (current.trieNodes[s.charAt(i) - 'a'] == null) {
                current.trieNodes[s.charAt(i) - 'a'] = new TrieNode(s.charAt(i));
            }
            current = current.next(s.charAt(i));
        }
        current.relevenceCount++;
    }

    public List<String> query(String s) {
        List<String> result = new ArrayList<>();

        TrieNode current = root;
        for (int i=0;i<s.length();i++) {
            if (current == null || current.next(s.charAt(i)) == null) {
                return result;
            } else {
                current = current.next(s.charAt(i));
            }
        }

        List<List<Character>> suffixes = new ArrayList<>();
        List<Character> suffix = new ArrayList<>();
        getSuffixes(current, suffixes, suffix);

//        System.out.println("Size of suff: " + suffixes.size());
//        for (String suff : suffixes) {
//            System.out.println("Suff: " + suff);
//            result.add(s + suff);
//        }

        return result;
    }

    private void getSuffixes(TrieNode trieNode, List<List<Character>> res, List<Character> r) {
        System.out.println("Inside getSuffixes for trieNode: " + trieNode.character);
        System.out.println("Res: " + res);
        System.out.println("r: " + r);
        TrieNode[] trieNodes = trieNode.trieNodes;
        if (isNoSuffix(trieNodes)) {
            res.add(r);
            r.remove(res.size() - 1);
            return;
        } else {
            for (TrieNode tN: trieNodes) {
                if (tN != null) {
                    r.add(tN.character);
                    getSuffixes(tN, res, r);
                }
            }
        }
    }

    private boolean isNoSuffix(TrieNode[] trieNodes) {
        for (TrieNode trieNode: trieNodes) {
            if (trieNode != null) {
                return false;
            }
        }
        return true;
    }

    public void updateRelevenceCount(final String s) {
        insert(s);
    }
}


class TrieNode {
    char character;
    int relevenceCount;
    final TrieNode[] trieNodes = new TrieNode[26];

    TrieNode(char c) {
        this.character = c;
    }

    public TrieNode next(final char c) {
        return trieNodes[c-'a'];
    }
}


class TrieTest {

    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        trie.insert("apply");
        trie.insert("apples");
        trie.insert("application");

        List<String> res = trie.query("app");
        for (String r : res) {
            System.out.println(r);
        }
    }
}