/*************************************************************************
 *  Compilation:  javac-algs4 -g Ex4abb.java
 *  Execution:    java-algs4 Ex4abb M
 * 
 * $ java-algs4 Ex4abb 10
 * LHS max = 210
 * (0, 0, 0, 0): 0 = 0 + 0 = 0 + 0
 * (3, 0, 1, 0): 3 = 3 + 0 = 3 + 0
 * (1, 1, 1, 0): 3 = 1 + 2 = 3 + 0
 * (4, 0, 0, 1): 4 = 4 + 0 = 0 + 4
 * (2, 1, 0, 1): 4 = 2 + 2 = 0 + 4
 * (7, 0, 1, 1): 7 = 7 + 0 = 3 + 4
 * (5, 1, 1, 1): 7 = 5 + 2 = 3 + 4
 * (6, 3, 2, 0): 24 = 6 + 18 = 24 + 0
 * (10, 3, 2, 1): 28 = 10 + 18 = 24 + 4
 * (9, 6, 3, 0): 81 = 9 + 72 = 81 + 0
 * $ time java-algs4 Ex4abb 100000 | wc -l
 *   567538
 * 
 * real	0m8.380s
 * user	0m7.075s
 * sys	0m4.038s
 *************************************************************************/

import edu.princeton.cs.algs4.*;

public class Ex4abb {

    public static void main(String[] args) {
	
        int M = Integer.parseInt(args[0]);

	int[][] lhs = {{0, 0, 2}, {1, 0, 0}, {0, 0, 0}};
	int[][] rhs = {{0, 0, 0, 0, 4}, {0, 0, 0, 0, 0}, 
			 {0, 0, 0, 0, 0}, {3, 0, 0, 0, 0},
                         {0, 0, 0, 0, 0}};
	Bifunction L = new Poly(lhs);
	Bifunction R = new Poly(rhs);
	
	long maxL = L.eval(M, M);	
	StdOut.println("LHS max = " + maxL);

        MinPQ<Pair> pqr = new MinPQ<Pair>();
	for (int i = 0; i <= M; i++)
	    pqr.insert(new Pair(i, 0, R, "RHS"));

	RedBlackBST<Long, Integer> st = new RedBlackBST<Long, Integer>();
	for (int b = 0; b <= M; b++) 
	    st.put(2L*b*b, b);
	
        while (!pqr.isEmpty()) {
            Pair s = pqr.delMin();
	    if (s.f() > maxL) break;

	    for (long B : st.keys(s.f() - M, s.f())) {
		long a = s.f() - B;
		int b = st.get(B);
		int c = s.i();
		int d = s.j();
		StdOut.print("(" + a + ", "+ b + ", " + c + ", " + d + "): ");
		StdOut.print(s.f() + " = " + a + " + " + 2*(long)b*b);
		StdOut.println(" = " + 3L*c*c*c + " + " + 4L*d*d*d*d);
	    }

	    Pair u = new Pair(s.i(), s.j() + 1, R, "RHS");
	    if (u.j() <= M) pqr.insert(u);
        }
    }
}