求调

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _rep(i,a,b) for(int i=(a);i>=(b);i--)
#define subset(i,x) for(int i=x;i;i=(i-1)&x)
#define pi pair<int,int>
#define arr(a) array<int,(a)>
#define RE return puts("0"),void()
#define cases(_) while((_)--) solve()
#define F fflush(stdout)
using namespace std;
const int mod=998244353;
inline void add(int& x,int y){x=(x%mod+y%mod+mod)%mod;}
inline void mul(int& x,int y){x=(x%mod)*(y%mod)%mod;}
inline void ckmin(int& x,int y){x=min(x,y);}
inline void ckmax(int& x,int y){x=max(x,y);}
const int N=1005,M=5000005;
int _=1,n,m,k,a[M];
int emp,cur,pos[N];
//pos=0: not in any stack, pos>=2: stack floor(pos/2)
deque<int> q[N];
vector<arr(3)> ans;
set<int> s;
// stack that allow join new element
inline void operate(int op,int s1,int s2){
	ans.push_back({op,s1,s2});
	if(op&1){
		if(!q[s1].empty() && q[s1].front()==s2) q[s1].pop_front();
		else q[s1].push_front(s2);
	}else{
		// assert(q[s1].size()),assert(q[s2].size()),assert(q[s1].back()==q[s2].back());
		if(q[s1].empty() || q[s2].empty()) exit(0);
		if(q[s1].back()==q[s2].back()){
			q[s1].pop_back(),q[s2].pop_back();
			for(int t:q[s1]) pos[t]++;
			for(int t:q[s2]) pos[t]++;
		}
	}
}
inline void upd(int x){
	// printf("!!! %d %d %d %d\n",x,pos[x],cur,s.size());
	if(!pos[x] && cur<2*n-2){
		int now=*s.begin();
		cur++,pos[x]=(now<<1|1)-q[now].size();
		operate(1,now,x);
		if(q[now].size()==2 && s.count(now)) s.erase(now);
	}else if(!(pos[x]&1) || (pos[x]&1 && q[pos[x]>>1].size()==1)){
		int now=(pos[x]>>1),tmp=(int)q[now].size();
		operate(1,now,x),pos[x]=0,cur--;
		if(tmp>=2 && q[now].size()==1) s.insert(now);
	}else{
		int now=(pos[x]>>1),tmp=(int)q[now].size();
		operate(1,emp,x),operate(2,now,emp),pos[x]=0,cur--;
		if(tmp>=2 && q[now].size()==1) s.insert(now);
	}
}
void solve(){
	scanf("%d%d%d",&n,&m,&k),emp=n,s.clear(),cur=0,ans.clear();
	rep(i,1,m) scanf("%d",&a[i]);
	rep(i,1,n-1) s.insert(i); 
	rep(i,1,m){
		int x=a[i];
		// printf("-> %d %d %d %d\n",i,x,pos[x],cur);
		// for(int t:q[1]) printf("%d ",t);
		// puts("");
		if(!pos[x] && cur==2*n-2){
			int nxt=-1;
			rep(o,i+1,m){
				if(pos[a[o]] && a[o]==q[pos[a[o]]>>1].back()){nxt=o;break;}
				if(a[o]==x){nxt=o;break;}
			}
			// assert(nxt!=-1);
			// printf("%d\n",nxt);
			if(a[nxt]==x){
				rep(o,i,nxt){
					if(o==i || o==nxt) operate(1,emp,a[o]);
					else upd(a[o]);
				}
			}else{
				int now=(pos[a[nxt]]>>1);
				int t=q[now].front(),cnt=0,tmp;
				rep(o,i+1,nxt) cnt+=(a[o]==t);
				if(cnt&1){
					// puts("Q");
					operate(1,emp,x),pos[x]=(emp<<1|1),cur++; 
					rep(o,i+1,nxt) upd(a[o]);
					if(s.count(now)) s.erase(now);
					s.insert(emp),emp=now;
				}else{
					operate(1,now,x),pos[x]=(now<<1)-1;
					rep(o,i+1,nxt-1){
						// printf("! %d\n",pos[a[o]]);
						if(a[o]==t) upd(a[o]),pos[a[o]]=(now<<1),cur++;
						else upd(a[o]);
					}
					operate(1,emp,a[nxt]),pos[a[nxt]]=0,operate(2,now,emp);
				}
			}
			i=nxt;
		}else upd(x);
	}
	// assert(cur==0);
	printf("%d\n",(int)ans.size());
	for(arr(3) t:ans){
		if(t[0]&1) printf("%d %d\n",t[0],t[1]);
		else printf("%d %d %d\n",t[0],t[1],t[2]);
	}
	rep(i,1,n) while(!q[i].empty()) q[i].pop_front();
	rep(i,1,m) a[i]=0;
	rep(i,1,k) pos[i]=0;
}
signed main(){
	scanf("%d",&_);
	cases(_);
	return 0;
}