#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;
    vector<int> list;
    vector<int> add;
    vector<int> ring;
    ring.resize(n,1);
    int i,j;
    int end;
    
    end=0;
    list.push_back(1);
    add.push_back(1);
    
    for(i=1;i<=n;i++){
        end=end*2+1;
        list.push_back(list[i-1]*2);
        add.push_back(add[i-1]*2);
    }
    answer.resize(end,vector<int>(2,0));

    for(i=0;i<answer.size();i++){
        for(j=0;j<n;j++){
            if(list[j]==i+1){
                list[j]+=add[j+1];
                answer[i][0]=ring[j];
                if(j%2==n%2){
                    switch(ring[j]){
                        case 1:
                            ring[j]=2;
                            break;
                        case 2:
                            ring[j]=3;
                            break;
                        case 3:
                            ring[j]=1;
                            break;
                    }
                }else{
                    switch(ring[j]){
                        case 1:
                            ring[j]=3;
                            break;
                        case 2:
                            ring[j]=1;
                            break;
                        case 3:
                            ring[j]=2;
                            break;
                    }
                }
                answer[i][1]=ring[j];
            }
        }
    }
    return answer;
}