Trie Stuff

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class trie {

    public static class Word implements Comparable<Word> {
        String str = null;
        long freq = 0;

        public Word(String s, long f) {
            str = s;
            freq = f;
        }

        @Override
        public int compareTo(Word arg) {
            return -(new Long(this.freq).compareTo(arg.freq));
        }
    }

    public static class Node {
        public ArrayList<Node> children = new ArrayList<Node>();
        public ArrayList<Word> suggestions = new ArrayList<Word>();

        public String str = null;

        public Node(String s) {
            str = s;
        }
    }

    public static void insert(Node root, Word w) {
        if (!w.str.startsWith(root.str)) {
            return;
        }

        root.suggestions.add(w);
        Collections.sort(root.suggestions);
        if (root.suggestions.size() > 3) {
            root.suggestions.remove(3);
        }

        boolean found = false;
        for (Node child : root.children) {
            if (w.str.startsWith(child.str)) {
                found = true;
                insert(child, w);
            }
        }
        if (found == false && w.str.length() > root.str.length()) {
            Node n = new Node(w.str.substring(0, root.str.length() + 1));
            root.children.add(n);
            insert(n, w);
        }
    }

    // O(length)
    public static ArrayList<Word> find(Node n, String s) {
        for(Node child : n.children) {
            if(s.startsWith(child.str)) {
                return find(child, s);
            }
        }
        if( s.length() > n.str.length() )
            return new ArrayList<Word>();
        else
            return n.suggestions;
    }

    public static void main(String[] args) {
        Node root = new Node("");

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        for( int i = 0; i < N; i++ ) {
            String str = in.next().toUpperCase();
            long freq = in.nextLong();
            insert(root, new Word(str, freq));
        }
        int Q = in.nextInt();
        for( int i = 0; i < Q; i++ ) {
            String str = in.next().toUpperCase();
            ArrayList<Word> ans = find(root, str);
            for(Word n : ans) {
                System.out.println(n.str);
            }
        }

        in.close();
    }
}


/*
TEST:
10
Project 5
Propane 3
Prudent 1
Plump 2
Apple 7
Amazon 2
Amazing 6
Testing 4
Test 5
Grape 6
10
P
> Project
> Propane
> Plump
Pr
> Project
> Propane
> Prudent
Pro
> Project
> Propane
Proj
> Project
Projk
>
Gr
> Grape
Ga
>
App
> Apple
Apl
>
A
> Apple
> Amazing
> Amazon

*/