public abstract class Hanoi {
    /**
     * @param n            the total number of rings.
     * @param source       the source tower.
     * @param intermediate the intermediate tower.
     * @param destination  the destination tower.
     * @return a list of steps to move all rings in the source tower to the destination tower.
     */
    public abstract List<String> solve(int n, char source, char intermediate, char destination);

    protected String getKey(int n, char source, char destination) {
        return n + ":" + source + "->" + destination;
    }
}

public class HanoiRecursive extends Hanoi {
    @Override
    public List<String> solve(int n, char source, char intermediate, char destination) {
        List<String> list = new ArrayList<>();
        solve(list, n, source, intermediate, destination);
        return list;
    }

    private void solve(List<String> list, int n, char source, char intermediate, char destination) {
        if (n == 0) return;
        solve(list, n - 1, source, destination, intermediate);
        list.add(getKey(n, source, destination));
        solve(list, n - 1, intermediate, source, destination);
    }
}

public class HanoiDynamic extends Hanoi {
    @Override
    public List<String> solve(int n, char source, char intermediate, char destination) {
        List<String> list = new ArrayList<>();
        solve(list, n, source, intermediate, destination, new HashMap<>());
        return list;
    }

    private void solve(List<String> list, int n, char source, char intermediate, char destination, Map<String, int[]> map) {
        if (n == 0) return;
        int fromIndex = list.size();
        int[] sub = map.get(getKey(n - 1, source, intermediate));

        if (sub != null) addAll(list, sub[0], sub[1]);
        else solve(list, n - 1, source, destination, intermediate, map);

        String key = getKey(n, source, destination);
        list.add(key);
        sub = map.get(getKey(n - 1, intermediate, destination));

        if (sub != null) addAll(list, sub[0], sub[1]);
        else solve(list, n - 1, intermediate, source, destination, map);

        if (!map.containsKey(key))
            map.put(key, new int[]{fromIndex, list.size()});
    }

    private void addAll(List<String> list, int fromIndex, int toIndex) {
        for (int i = fromIndex; i < toIndex; i++)
            list.add(list.get(i));
    }
}

public interface Fibonacci {
    int get(int k);
}

public class FibonacciRecursive implements Fibonacci {
    @Override
    public int get(int k) {
        return switch (k) {
            case 0 -> 0;
            case 1 -> 1;
            default -> get(k - 1) + get(k - 2);
        };
    }
}

public class FibonacciDynamic implements Fibonacci {
    @Override
    public int get(int k) {
        return getAux(k, createTable(k));
    }
    
    private int[] createTable(int k) {
        int[] table = new int[k + 1];
        table[0] = 0;
        table[1] = 1;
        Arrays.fill(table, 2, k + 1, -1);
        return table;
    }

    private int getAux(int k, int[] table) {
        if (table[k] >= 0) return table[k];
        return table[k] = getAux(k - 1, table) + getAux(k - 2, table);
    }
}

public class FibonacciIterative implements Fibonacci {
    @Override
    public int get(int k) {
        if (k < 2) return k;
        int f0 = 0, f1 = 1, f2;

        for (int i = 2; i < k; i++) {
            f2 = f0 + f1;
            f0 = f1;
            f1 = f2;
        }

        return f0 + f1;
    }
}

public abstract class LCS {
    /**
     * @param a the first string.
     * @param b the second string.
     * @return a longest common sequence of the two specific strings.
     */
    public String solve(String a, String b) {
        return solve(a.toCharArray(), b.toCharArray(), a.length() - 1, b.length() - 1);
    }

    /**
     * @param c the first array of characters.
     * @param d the second array of characters.
     * @param i the index of the character in {@code c} to be compared.
     * @param j the index of the character in {@code d} to be compared.
     * @return a longest common sequence of the two specific strings.
     */
    protected abstract String solve(char[] c, char[] d, int i, int j);
}

public class LCSRecursive extends LCS {
    @Override
    protected String solve(char[] c, char[] d, int i, int j) {
        if (i < 0 || j < 0) return "";
        if (c[i] == d[j]) return solve(c, d, i - 1, j - 1) + c[i];

        String c1 = solve(c, d, i - 1, j);
        String d1 = solve(c, d, i, j - 1);
        return (c1.length() > d1.length()) ? c1 : d1;
    }
}

public class LCSDynamic extends LCS {
    @Override
    protected String solve(char[] c, char[] d, int i, int j) {
        return solve(c, d, i, j, createTable(c, d));
    }

    /**
     * @param c the first string.
     * @param d the second string.
     * @return the dynamic table populated by estimating the # of LCSs in the grid of the two specific strings.
     */
    protected int[][] createTable(char[] c, char[] d) {
        final int N = c.length, M = d.length;
        int[][] table = new int[N][M];

        for (int i = 1; i < N; i++)
            for (int j = 1; j < M; j++)
                table[i][j] = (c[i] == d[j]) ? table[i - 1][j - 1] + 1 : Math.max(table[i - 1][j], table[i][j - 1]);

        return table;
    }
}

protected String solve(char[] c, char[] d, int i, int j, int[][] table) {
    if (i < 0 || j < 0) return "";
    if (c[i] == d[j])  return solve(c, d, i - 1, j - 1, table) + c[i];
    
    if (i == 0) return solve(c, d, i, j - 1, table);
    if (j == 0) return solve(c, d, i - 1, j, table);
    return (table[i - 1][j] > table[i][j - 1]) ? solve(c, d, i - 1, j, table) : solve(c, d, i, j - 1, table);
}