/* -----------------------------------------------------------------
Mal'tsev constraints in C++
by Albert Atserias.

Version 1.0: 17/01/2006.
Version 1.1: 23/01/2006.

Description: Implementation of the polynomial-time algorithm due to 
Bulatov and Dalmau for solving constraint-satisfaction problems 
whose constraints are all closed under the same Mal'tsev operation. 
The running time is cubic (perhaps quartic) on the number of 
variables and the size of the domain.

The implementation is not particularly tuned for efficiency.
The only motivation I had for implementing the algorithm was
to understand it better.

This software is written exclusively for academic purposes.
----------------------------------------------------------------- */

#include <iostream>
#include <vector>
#include <set>

using namespace std;

typedef vector< vector< vector<int> > > ternary_fun;

typedef vector<int> tuple;

typedef set<tuple> relation;

typedef set<tuple>::iterator iter;
	
struct constraint {

    int arity;
    vector<int> variables;
    relation tuples;
    
};


/* -----------------------------------------------------------------
Class: csp_maltsev
Description: Main class implementing a csp-solver when all
constraints are closed under the same Mal'tsev operation.
It implements the polynomial-time algorithm by Bulatov and Dalmau.

Fields:
n: number of variables of the instance
m: size of the domain
constraints: the vector of constraints
maltsev_op: the Mal'tsev operation under which all constraints are 
  closed.
----------------------------------------------------------------- */



class csp_maltsev {

    int n;
    int m;
    vector<constraint> constraints;
    ternary_fun maltsev_op;

public: 

    /* -----------------------------------------------------------------
    Constructor: csp_maltsev()
    Description: This constructor is to be used when the instance is 
    obtained from the standard input using the method read_from_stdin().
    ----------------------------------------------------------------- */
    csp_maltsev() { }


    /* -----------------------------------------------------------------
    Constructor: csp_maltsev(n,m,op)
    Description: This constructor is to be used when the instance is 
    given explicitely, except for the constraints that are given one by 
    one using the method impose_new_constraint(constraint& c).
    ----------------------------------------------------------------- */
    csp_maltsev(int n, int m, ternary_fun& op) {

        this->n = n; 
	this->m = m; 
        maltsev_op = op;
        constraints=vector<constraint>(0);
        solution = fullrelation(n,m);

    }


    /* -----------------------------------------------------------------
    Constructor: csp_maltsev(n,m,c,op)
    Description: This constructor is to be used when the whole instance 
    is given explicitely. It does not solve the instance. It does not 
    initialize the current solution. Use solve() to solve the instance.
    ----------------------------------------------------------------- */
    csp_maltsev(int n, int m, vector<constraint>& c, ternary_fun& op) {

        this->n = n; 
	this->m = m; 
        maltsev_op = op;
        constraints=c;

    }
    

    /* -----------------------------------------------------------------
    Method: void solve()
    Description: Solves the instance by initializing the current 
    solution to the full relation and by imposing all constraints one 
    after the other in the order they appear in the vector constraints.
    ----------------------------------------------------------------- */
    void solve() {
    
        solution = fullrelation(n,m);
        int q = constraints.size();
        for (int i=0; i<q; ++i)
	    impose_constraint(constraints[i]);
    
    }


    /* -----------------------------------------------------------------
    Method: impose_new_constraint(c)
    Description: Adds the constraint c to the vector of constraints and 
    imposes it to the current solution. Precondition: the current 
    solution must be initialized.
    ----------------------------------------------------------------- */
    void impose_new_constraint(constraint& c) {

        constraints.push_back(c);
	impose_constraint(c);
	
    }

    /* -----------------------------------------------------------------
    Method: impose_constraint(c)
    Description: Imposes the constraint c to the current solution. 
    Precondition: the current solution must be initialized.
    ----------------------------------------------------------------- */
    void impose_constraint(constraint& c) {

        for (int j=0; j<c.arity; ++j) {
	    constraint cc;
	    cc.arity = j+1;
	    cc.variables = vector<int>(j+1);
	    vector<int> v = vector<int>(j+1);
	    for (int i=0; i<j+1; ++i) {
	        cc.variables[i] = c.variables[i];
		v[i] = i;
	    }
	    cc.tuples = projection(c.tuples,v);	
 	    solution = next_beta(solution,cc);
	}

    }
    

    /* -----------------------------------------------------------------
    Method: has_solutions()
    Description: Returns true of the current solution is non-empty. 
    Precondition: the current solution must be initialized.
    ----------------------------------------------------------------- */
    bool has_solutions() {
        return solution.tuples.empty();
    }

    
    /* -----------------------------------------------------------------
    Method: one_solution()
    Description: Returns one solution. Precondition: the current 
    solution must be initialized and non-empty.
    ----------------------------------------------------------------- */
    tuple one_solution() {    
        return *solution.tuples.begin();    
    }
    
    
    /* -----------------------------------------------------------------
    Method: all_solutions()
    Description: Returns the set of all solutions. The returned set 
    could be empty. Precondition: the current solution must be 
    initialized.
    ----------------------------------------------------------------- */
    relation all_solutions() {

        relation U = solution.tuples;
	int q;
	do {
	    q = 0;
	    relation N = U;
            for (iter it1=U.begin(); it1!=U.end(); it1++)
            for (iter it2=U.begin(); it2!=U.end(); it2++)
            for (iter it3=U.begin(); it3!=U.end(); it3++) {
	        tuple t1 = *it1;
		tuple t2 = *it2;
		tuple t3 = *it3;
	        tuple t = apply_op(t1,t2,t3);
		if (N.find(t) == N.end()) {
		    N.insert(t); q++;
		}		
	    }	
	    U = N;
        } while (q > 0);	
	return U;

    }

    
    /* -----------------------------------------------------------------
    Method: read_from_stdin()
    Description: Reads an instance from the standard input stream. It 
    expects the following format (without the separating comas): number 
    of variables, size of the domain, the maltsev operation given by its 
    table (a sequence op 4-tuples a,b,c,op(a,b,c)), number of 
    constraints, sequence of constraints each given by the following 
    data: arity, tuple of variables of the constraint, number of valid 
    tuples, sequence of valid tuples.
    ----------------------------------------------------------------- */
    void read_from_stdin() {

        int aa,bb,cc,q,v,p;
        cin >> n >> m;
        maltsev_op = vector< vector< vector<int> > >(3,
	    vector< vector<int> >(3,vector<int>(3)));
        for (int a=0; a<m; ++a)
        for (int b=0; b<m; ++b)
        for (int c=0; c<m; ++c) {
            cin >> aa >> bb >> cc >> v;
	    maltsev_op[aa][bb][cc] = v;
        }
        cin >> q;
	constraints = vector<constraint>(q);
        for (int i=0; i<q; ++i) {
            constraint c;
	    cin >> c.arity; 
	    c.variables = vector<int>(c.arity);
	    for (int j=0; j<c.arity; ++j) cin >> c.variables[j];
	    c.tuples = relation();
	    cin >> p;
	    for (int j=0; j<p; ++j) {
    	        tuple t = tuple(c.arity); 
	        for (int k=0; k<c.arity; ++k) cin >> t[k];
	        c.tuples.insert(t);	
	    }
	    constraints[i] = c;
	}    
    
    }
    
    
private:

    /* -----------------------------------------------------------------
    Private data structure: struct compact
    Description: Data structure for describing the compact 
    representation of a relation that is closed under a Mal'tsev 
    operation.
    
    Fields:
    arity: self-explanatory.
    tuples: a subset of the tuples of the true relation.
    W1[i][a][b]: first witness for (i,a,b), if any.
    W2[i][a][b]: second witness for (i,a,b), if any.
    ----------------------------------------------------------------- */
    struct compact {

	typedef vector< vector< vector<tuple> > > witnesses;
	
	int arity;
	relation tuples;
	witnesses W1;
	witnesses W2;

	compact() {}

	compact(int n, int m) {

            arity = n; 
            tuples = relation();
            W1 = vector< vector< vector<tuple> > >(n,vector<
	      vector<tuple> >(m,vector<tuple>(m,tuple(n))));
            W2 = vector< vector< vector<tuple> > >(n,vector<
	      vector<tuple> >(m,vector<tuple>(m,tuple(n))));

	}

    };


    /* -----------------------------------------------------------------
    Private field: solution
    Description: Current partial solution in compact representation.
    ----------------------------------------------------------------- */
    compact solution;


    /* -----------------------------------------------------------------
    Private function: apply_op(t1,t2,t3)
    Description: Applies the Mal'tsev operation component-wise to t1,t2,
    t3. Precondition: all tuples must be of the same length.
    ----------------------------------------------------------------- */
    tuple apply_op(tuple& t1, tuple& t2, tuple& t3) {

        int n = t1.size();
	tuple t = vector<int>(n);
	for (int i=0; i<n; ++i)
	    t[i] = maltsev_op[t1[i]][t2[i]][t3[i]];
	return t;
    
    }


    /* -----------------------------------------------------------------
    Private function: tuple_projection(t,I)
    Description: Projects tuple t with respect to the index vector I. 
    Precondition: each I[i] must be a valid index of the tuple.
    ----------------------------------------------------------------- */
    tuple tuple_projection(tuple& t, vector<int>& I) {
    
        int n = I.size();
        tuple tt = vector<int>(n);
	for (int i=0; i<n; ++i)
	    tt[i] = t[I[i]];
	return tt;
	
    }
        

    /* -----------------------------------------------------------------
    Private function: projection(A,I)
    Description: Projects all tuples of the relation A with respect to 
    the index vector I. Precondition: each I[i] must be a valid index of 
    the tuples in A.
    ----------------------------------------------------------------- */
    relation projection(relation& A, vector<int>& I) {
    
        relation B = relation();
	for (iter it=A.begin(); it!=A.end(); it++) {
	    tuple t = *it;
	    tuple tt = tuple_projection(t,I);
	    B.insert(tt);
	}
	return B;
	
    }

    
    /* -----------------------------------------------------------------
    Private function: extend(c,i,a)
    Description: Extends the constraint c with one more variable 
    numbered i, and extends the set of valid tuples by appending them a 
    to the end. Precondition: the obvious one.
    ----------------------------------------------------------------- */
    constraint extend(constraint& c, int i, int a) {
    
        constraint cc;	
	cc.arity = c.arity+1; 
	cc.variables = c.variables;
	cc.variables.push_back(i);
	cc.tuples = relation();	
	for (iter it=c.tuples.begin(); it!=c.tuples.end(); it++) {
	    tuple t = *it; 
	    t.push_back(a);
	    cc.tuples.insert(t);
	}
	return cc;
	            
    }
    


    /* -----------------------------------------------------------------
    Private function: fullrelation(n,m)
    Description: Returns a compact representation of the full relation,
    that is, {0,...,m-1}^n.
    ----------------------------------------------------------------- */
    compact fullrelation(int n, int m) {
    
        compact r(n,m);
        for (int i=0; i<n; ++i) 
	for (int a=0; a<m; ++a)
	for (int b=0; b<m; ++b) {
            tuple t1 = vector<int>(n,0);
	    tuple t2 = vector<int>(n,0);
	    t1[i] = a; t2[i] = b;
	    r.tuples.insert(t1); 
	    r.W1[i][a][b] = t1; 
	    if (a != b) {
	        r.tuples.insert(t2);    
	        r.W2[i][a][b] = t2;
	    }
	}
	return r;
	
    }


    /* -----------------------------------------------------------------
    Private function: non_empty(r,c)
    Description: If the relation represented by r contains a tuple that 
    satisfies the constraint c, it returns it. Otherwise it returns an 
    empty tuple.
    ----------------------------------------------------------------- */
    tuple non_empty(compact& r, constraint& c) {
    
        relation U = r.tuples;	
        int q;
	do {
	    q = 0;
	    relation P = projection(U,c.variables);
	    relation N = U;
            for (iter it1=U.begin(); it1!=U.end(); it1++)
            for (iter it2=U.begin(); it2!=U.end(); it2++)
            for (iter it3=U.begin(); it3!=U.end(); it3++) {
	        tuple t1 = *it1;
		tuple t2 = *it2;
		tuple t3 = *it3;
	        tuple t = apply_op(t1,t2,t3);
		tuple tt = tuple_projection(t,c.variables);
		if (c.tuples.find(tt) != c.tuples.end()) return t;
		if (P.find(tt) == P.end() and N.find(t) == N.end()) {
		    N.insert(t); q++;
		}		
	    }	
	    U = N;
        } while (q > 0);
	return vector<int>();
	
    }


    /* -----------------------------------------------------------------
    Private function: fix_values(r,t,l)
    Description: Given a compact representation r of a relation A, given 
    a tuple t, and given an index l, it returns a compact representation 
    of the set of all tuples in A that agree with t in their first l
    positions.
    ----------------------------------------------------------------- */
    compact fix_values(compact& r, tuple& t, int l) {
    
        compact s = r;
	for (int j=0; j<l+1; ++j) {
	
	    compact ss(n,m); 
	    
	    constraint c;
	    c.arity = 2;
	    c.variables = vector<int>(2);
	    c.variables[0] = j;
	    c.tuples = relation();
	    
	    tuple tt = vector<int>(2);
	    tt[0] = t[j];
	    
            for (int i=j+1; i<n; ++i)
            for (int a=0; a<m; ++a)
            for (int b=0; b<m; ++b) {

		c.variables[1] = i;
		tt[1] = a;
		c.tuples.insert(tt);
		
		tuple t1 = non_empty(s,c);
		tuple t2 = s.W1[i][a][b];
		tuple t3 = s.W2[i][a][b];
		if (t1.size()>0 and t2.size()>0 and t3.size()>0) {
		    ss.tuples.insert(t1); 
		    ss.W1[i][a][b] = t1;
		    if (a != b) {
		        tuple t4 = apply_op(t1,t2,t3);
  		        ss.tuples.insert(t4);
		        ss.W2[i][a][b] = t4;
		    }
		}
		
	    }
	    s = ss;

	}

	return s;
    
    }

        
    /* -----------------------------------------------------------------
    Private function: next_beta(r,cc)
    Description: Given a compact representation r of a relation A and 
    given a constraint cc, it returns a compact representation of the 
    result of imposing the constraint cc on A. It is called next_beta 
    because it is used as an auxiliary function in the method 
    impose_constraint.
    ----------------------------------------------------------------- */
    compact next_beta(compact& r, constraint& cc) {
    
        compact s(n,m);

        for (int i=0; i<n; ++i)
        for (int a=0; a<m; ++a)
        for (int b=0; b<m; ++b) {

            compact rr = r;
            constraint cc1 = extend(cc,i,a);
            constraint cc2 = extend(cc,i,b);		
            tuple t1 = non_empty(rr,cc1);
            if (t1.size()>0) {
                rr = fix_values(rr,t1,i-1);
                tuple t2 = non_empty(rr,cc2);
                if (t2.size()>0) {
                    s.tuples.insert(t1); 
		    s.W1[i][a][b] = t1;
		    if (a != b) {
		        s.tuples.insert(t2);
		        s.W2[i][a][b] = t2;
		    }
                }
            }

        }

        return s;

    }


};



/* -----------------------------------------------------------------
A test program.
Description: Reads an instance from the standard input, it solves 
it, it obtains the collection of all solutions, and it prints them 
out in the standard output.
----------------------------------------------------------------- */
int main() {

    csp_maltsev instance = csp_maltsev();
    instance.read_from_stdin();
    instance.solve();
    relation r = instance.all_solutions();
    for (iter it=r.begin(); it!=r.end(); it++) {
	for (int i=0; i<(int)(*it).size(); ++i) 
	    cout << (*it)[i] << " ";
        cout << endl;
    }
    cout << endl;

}