// User function Template for Java
class Node
{
    int i;
    int j;
    String str;
    
    Node(int i, int j, String str)
    {
        this.i = i;
        this.j = j;
        this.str = str;
    }
}

class Solution {
    // TreeSet automatically keeps elements sorted lexicographically.
    Set<String> set = new TreeSet<>();
    
    /** Memoization **/
    public List<String> allLCS(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        // step-1 create a matrix
        int[][] t = new int[n+1][m+1];
        
        // step-2 initialise the matrix acc. to base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                // Base case: If either string is empty, LCS is 0.
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }
        
        // step-3 convert recursive code to iterative
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                // If the current characters match, add 1 to the previous LCS length.
                if(s1.charAt(i-1) == s2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                // If the current characters do not match, take the maximum of the LCS
                // when one character from either string is excluded.
                else
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
            }
        }
        
        // print all LCS
        printAllLCS(s1, s2, n, m, t, "");
        List<String> list = new ArrayList<>();
        list.addAll(set);
        return list;
    }
    
    public void printAllLCS(String s1, String s2, int i, int j, int[][] t, String str)
    {
        if(i == 0 || j == 0)
        {
            set.add(new StringBuilder(str).reverse().toString());
            return;
        }
        
        if(s1.charAt(i-1) == s2.charAt(j-1))
        {
            printAllLCS(s1, s2, i-1, j-1, t, str + s1.charAt(i-1));
        }
        else
        {
            // If both equal → explore both paths (this creates multiple LCS).
            if(t[i-1][j] >= t[i][j-1])
                printAllLCS(s1, s2, i-1, j, t, str);
                
            if(t[i][j-1] >= t[i-1][j])
                printAllLCS(s1, s2, i, j-1, t, str);
        }
    }
    
    /** Top-Down Approach **/
    public List<String> allLCS(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        // step-1 create a matrix
        int[][] t = new int[n+1][m+1];
        
        // step-2 initialise the matrix acc. to base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                // Base case: If either string is empty, LCS is 0.
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }
        
        // step-3 convert recursive code to iterative
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                // If the current characters match, add 1 to the previous LCS length.
                if(s1.charAt(i-1) == s2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                // If the current characters do not match, take the maximum of the LCS
                // when one character from either string is excluded.
                else
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
            }
        }
 
        Stack<Node> st = new Stack<>();
        st.push(new Node(n, m, ""));
        
        while(!st.isEmpty())
        {
            Node curr = st.pop();
            int i = curr.i;
            int j = curr.j;
            String s = curr.str;
            
            if(i == 0 || j == 0)
            {
                set.add(new StringBuilder(s).reverse().toString());
                continue;
            }
            
            if(s1.charAt(i-1) == s2.charAt(j-1))
                st.push(new Node(i-1, j-1, s + s1.charAt(i-1)));
                
            else
            {
                // explore both paths
                if(t[i-1][j] >= t[i][j])
                    st.push(new Node(i-1, j, s));
                    
                if(t[i][j-1] >= t[i][j])
                    st.push(new Node(i, j-1, s));
            }
        }
        List<String> list = new ArrayList<>();
        list.addAll(set);
        return list;
    }
}