/*
 * The following program can be used to verify the base cases of the inductive
 * proofs of Lemmas 16 and 25 in the paper.
 *
 * This program generates, for n >= 7, the n+1 nontrivial equivalence classes of
 * classes of S_n under the {1234-3412} pattern-replacement equivalence.
 * Different classes are separated by new lines in the output.
 *
 * Please contact Alexander Zhang, creator of this program, with any questions.
 */

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <list>
#include <deque>

using namespace std;

int factorial(int a){
    int j = 1;
    for (int i=1; i<=a; i++)
        j*=i;
    return j;
}
int N = 7; // the value of n
int factorialN = factorial(N);
int main(){
    vector<int> letters;
    for (int i=1; i<=N; i++)
        letters.push_back(i);
    vector<string> permutations;
    map<string, int> perm_indices;
    do {
        string perm_string="";
        for (int i : letters)
            perm_string+=to_string(i);
        perm_indices.insert(make_pair(perm_string,permutations.size()));
        permutations.push_back(perm_string);
    } while ( next_permutation(letters.begin(),letters.end()) );
    set<string> leaders;
    set<int> indices_to_skip;
    for (int k=2; k<=N; k++){
        string leader = "";
        for (int i=1; i<k; i++){
            leader+=to_string(k-i);
        }
        for (int i=k; i<=N; i++){
            leader+=to_string(N+k-i);
        }
        leaders.insert(leader);
    }
    vector<string> adjacency_list[factorialN+1];
    for (int i=0; i<factorialN; i++){
        string perm = permutations[i];
        bool has_neighbor = false;
        for (int a=0; a<N; a++){
            for (int b=a+1; b<N; b++){
                for (int c=b+1; c<N; c++){
                    for (int d=c+1; d<N; d++){
                        int w = perm[a];
                        int x = perm[b];
                        int y = perm[c];
                        int z = perm[d];
                        string transposed=perm;
                        if (w<x&&x<y&&y<z){
                            has_neighbor = true;
                            transposed[a]=y;
                            transposed[b]=z;
                            transposed[c]=w;
                            transposed[d]=x;
                        }
                        if (y<z&&z<w&&w<x){
                            has_neighbor = true;
                            transposed[a]=y;
                            transposed[b]=z;
                            transposed[c]=w;
                            transposed[d]=x;
                        }
                        if (transposed != perm)
                            adjacency_list[perm_indices[perm]].push_back(transposed);
                    }
                }
            }
        }
        if (!has_neighbor){
            indices_to_skip.insert(i);
        }
    }
    vector<bool> visited(factorialN, false);
    for (int i=0; i<factorialN; i++){
        if (visited[i]||indices_to_skip.count(i)>0)
            continue;
        visited[i]=true;
        string curr_perm = permutations[i];
        if (stoi(curr_perm)/((int)pow(10, N-1))==N||stoi(curr_perm)%10==1)
            continue;
        queue<pair<int, string> > q;
        q.push(make_pair(i, permutations[i]));
        bool nontrivial = false;
        while (!q.empty()){
            pair<int, string> curr_pair = q.front();
            q.pop();
            int index = curr_pair.first;
            string perm_string = curr_pair.second;
            for (string s : adjacency_list[index]){
                int adj_index = perm_indices[s];
                if (visited[adj_index])
                    continue;
                visited[adj_index] = true;
                q.push(make_pair(adj_index, s));
                nontrivial = true;
            }
            if (nontrivial)
                cout<<perm_string<<" ";
        }
        if (nontrivial)
            cout<<endl<<endl;
    }
}