class SearchEngine{

    private static class Pair implements Comparable<Pair>{
        String s, t;

        public Pair(String s, String t) {
            this.s = s;
            this.t = t;
        }


        @Override
        public int compareTo(Pair o) {
            if (s.equals(o.s)) {
                return t.compareTo(o.t);
            }
            else {
                return s.compareTo(o.s);
            }
        }
    }

    private class PairForSort implements Comparable<PairForSort>{

        String s;
        Double v;

        @Override
        public int compareTo(PairForSort o) {
            return v.compareTo(o.v);
        }

        public PairForSort(String s, Double v) {
            this.s = s;
            this.v = v;
        }
    }

    private static Map<Pair, Integer> res = new TreeMap<>();

    static int levensteinDelta(String s, String t){
        if (res.containsKey(new Pair(s, t))){
            return res.get(new Pair(s, t));
        }
        if (s.equals(t)){
            return 0;
        }
        if (s.length() == 0 || t.length() == 0){
            return s.length() + t.length();
        }
        int result =  Math.min(Math.min(levensteinDelta(s.substring(0, s.length()-1), t) + 1, levensteinDelta(s, t.substring(0, t.length()-1)) + 1),
                levensteinDelta(s.substring(0, s.length()-1), t.substring(0, t.length()-1)) + (s.charAt(s.length() - 1) == t.charAt(t.length() - 1) ? 0 : 1));
        res.put(new Pair(s, t), result);
        return result;
    }

    static int maxCommonSubstring(String s, String t){
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            for (int j = 0; j <= t.length(); j++) {
                if (i == 0 || j == 0) dp[i][j] = 0;
                else {
                    if (s.charAt(i - 1) == t.charAt(j - 1)){
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    }
                    else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
        }
        return dp[s.length()][t.length()];
    }

    ArrayList<String> all = new ArrayList<>();

    ArrayList<String> searchRequest(String search){
        search = search.toLowerCase();
        ArrayList<PairForSort> result = new ArrayList<>();
        for (int i = 0; i < all.size(); i++) {
            String current = all.get(i).toLowerCase();
            int lev = levensteinDelta(current, search);
            double met = (maxCommonSubstring(current, search) + 0.0) / Math.min(search.length(), current.length());
            if (lev <= 3 || met > 0.8) {
                result.add(new PairForSort(current, lev / met));
            }
        }
        result.sort(PairForSort::compareTo);
        ArrayList<String> ret = new ArrayList<>();
        for (PairForSort p : result) {
            ret.add(p.s);
        }
        return ret;
    }

    void addElement(String s){
        if (!s.isEmpty()){
            all.add(s);
        }
    }

}