#include <bits/stdc++.h>
using namespace std;
#define ll long long
#ifdef _DEBUG
void init(int T);
void orderCoins();
void answer(int C[]);
int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
#else
#include "scales.h"
#endif
void init(int T) {}
int excl(vector<int> a, vector<int> b)
{
for (int x : a)
{
bool found = false;
for (int y : b)
found |= x == y;
if (!found)
return x;
}
assert(false);
return -1;
}
vector<int> order;
// void insert(int l, int r, int x)
// {
// if (l + 1 == r)
// {
// int median = getMedian(x, order[l], order[r]);
// if (median == order[l])
// order.insert(order.begin() + l, x);
// else if (median == order[r])
// order.insert(order.begin() + r + 1, x);
// else
// order.insert(order.begin() + r, x);
// }
// else if (l + 2 == r)
// {
// int median = getMedian(x, order[l], order[r]);
// if (median == order[l])
// order.insert(order.begin() + l, x);
// else if (median == order[r])
// order.insert(order.begin() + r + 1, x);
// else
// insert(l, r - 1, x);
// }
// else
// {
// int median = getMedian(x, order[l], order[r]);
// if (median == order[l])
// order.insert(order.begin() + l, x);
// else if (median == order[r])
// order.insert(order.begin() + r + 1, x);
// else
// insert(l + 1, r - 1, x);
// }
// }
void orderCoins()
{
vector<int> shuf = {1, 2, 3, 4, 5, 6};
// random_shuffle(shuf.begin(), shuf.end());
shuf.insert(shuf.begin(), 0);
vector<int> order1, order2;
{
int smallest = getLightest(shuf[1], shuf[2], shuf[3]);
int biggest = getHeaviest(shuf[1], shuf[2], shuf[3]);
int middle = excl({shuf[1], shuf[2], shuf[3]}, {smallest, biggest});
order1 = {smallest, middle, biggest};
}
{
int smallest = getLightest(shuf[4], shuf[5], shuf[6]);
int biggest = getHeaviest(shuf[4], shuf[5], shuf[6]);
int middle = excl({shuf[4], shuf[5], shuf[6]}, {smallest, biggest});
order2 = {smallest, middle, biggest};
}
vector<int> output;
while (output.size() < 6)
{
if (order1.size() < order2.size()) {
swap(order1, order2);
}
if (order2.size() == 0) {
for (int x : order1)
output.push_back(x);
order1.clear();
continue;
}
if (order1.size() == 1) {
int median = getMedian(order1[0], order2[0], output.back());
if (median == order1[0]) {
output.push_back(order1[0]);
order1.erase(order1.begin());
output.push_back(order2[0]);
order2.erase(order2.begin());
} else if (median == order2[0]) {
output.push_back(order2[0]);
order2.erase(order2.begin());
output.push_back(order1[0]);
order1.erase(order1.begin());
} else {
assert(false);
}
continue;
}
int median = getMedian(order1[0], order1[1], order2[0]);
if (median == order2[0]) {
output.push_back(order1[0]);
order1.erase(order1.begin());
output.push_back(order2[0]);
order2.erase(order2.begin());
} else if (median == order1[1]) {
output.push_back(order1[0]);
order1.erase(order1.begin());
output.push_back(order1[0]);
order1.erase(order1.begin());
} else if (median == order1[0]) {
output.push_back(order2[0]);
order2.erase(order2.begin());
}
}
answer(&output[0]);
}
#ifdef _DEBUG
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXN 6
#define MAX_ANSWER_CALLS 1
static int realC[MAXN];
static int ind[MAXN];
static int numQueries;
static int numAnswerCalls;
static int arr[300];
static int arraySize;
static int ptr;
static void readAll()
{
ptr = 0;
arraySize = 0;
int x;
cin >> x;
arr[arraySize++] = x;
for (int i = 0; i < arr[0] * 6; i++)
{
cin >> x;
arr[arraySize++] = x;
assert(arraySize <= 300);
}
}
static int readInt()
{
assert(ptr < arraySize);
int res = arr[ptr++];
return res;
}
static void initNewTest()
{
for (int i = 0; i < MAXN; i++)
{
realC[i] = readInt();
realC[i]--;
ind[realC[i]] = i;
}
numQueries = 0;
numAnswerCalls = 0;
}
void answer(int C[])
{
int i;
numAnswerCalls++;
if (numAnswerCalls > MAX_ANSWER_CALLS)
return;
for (i = 0; i < 6; i++)
printf("%d ", C[i]);
printf("%d\n", numQueries);
}
static void checkQuery(int A, int B, int C, int D)
{
if (D == -1)
{
if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6)
assert(0);
if (A == B || B == C || A == C)
assert(0);
}
else
{
if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6)
assert(0);
if (A == B || A == C || A == D || B == C || B == D || C == D)
assert(0);
}
}
int getMedian(int A, int B, int C)
{
numQueries++;
checkQuery(A, B, C, -1);
A--;
B--;
C--;
if (ind[B] < ind[A] && ind[A] < ind[C])
return A + 1;
if (ind[C] < ind[A] && ind[A] < ind[B])
return A + 1;
if (ind[A] < ind[B] && ind[B] < ind[C])
return B + 1;
if (ind[C] < ind[B] && ind[B] < ind[A])
return B + 1;
return C + 1;
}
int getHeaviest(int A, int B, int C)
{
numQueries++;
checkQuery(A, B, C, -1);
A--;
B--;
C--;
if (ind[A] > ind[B] && ind[A] > ind[C])
return A + 1;
if (ind[B] > ind[A] && ind[B] > ind[C])
return B + 1;
return C + 1;
}
int getLightest(int A, int B, int C)
{
numQueries++;
checkQuery(A, B, C, -1);
A--;
B--;
C--;
if (ind[A] < ind[B] && ind[A] < ind[C])
return A + 1;
if (ind[B] < ind[A] && ind[B] < ind[C])
return B + 1;
return C + 1;
}
int getNextLightest(int A, int B, int C, int D)
{
int allLess = 1;
numQueries++;
checkQuery(A, B, C, D);
A--;
B--;
C--;
D--;
if (ind[A] > ind[D] || ind[B] > ind[D] || ind[C] > ind[D])
allLess = 0;
if (allLess == 1)
{
if (ind[A] < ind[B] && ind[A] < ind[C])
return A + 1;
if (ind[B] < ind[A] && ind[B] < ind[C])
return B + 1;
return C + 1;
}
if (ind[A] > ind[D])
{
if ((ind[A] < ind[B] || ind[B] < ind[D]) &&
(ind[A] < ind[C] || ind[C] < ind[D]))
return A + 1;
}
if (ind[B] > ind[D])
{
if ((ind[B] < ind[A] || ind[A] < ind[D]) &&
(ind[B] < ind[C] || ind[C] < ind[D]))
return B + 1;
}
return C + 1;
}
int main()
{
readAll();
fclose(stdin);
int T, i;
T = readInt();
init(T);
for (i = 1; i <= T; i++)
{
initNewTest();
orderCoins();
}
return 0;
}
#endif
