#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
bool test(vector<int> &phs, vector<int> &ans, vector<int> &rs, int &ind) {
int l = 0, r = phs.size() - 1;
int anss = INT_MAX;
while (l <= r) {
int m = (l + r) >> 1;
vector<int> quer;
for (int i = 0; i <= m; i++)
quer.push_back(phs[i] + 1);
for (int i = ind; i < min(ind + 8, (int)rs.size()); i++) {
for (int j = 0; j < (1 << (i - ind)); j++) {
quer.push_back(rs[i] + 1);
}
}
int val = query_sample(quer);
if (val == quer.size())
l = m + 1;
else {
anss = min(anss, m);
r = m - 1;
for (int i = ind; i < min(ind + 8, (int)rs.size()); i++) {
if (val & (1 << (i - ind)))
ans[rs[i]] = 2;
else
ans[rs[i]] = 1;
}
ind += 8;
}
}
ans[phs[anss]] = 3;
vector<int> newphs;
for (int i = 0; i < anss; i++)
newphs.push_back(phs[i]);
for (int i = anss + 1; i < phs.size(); i++)
newphs.push_back(phs[i]);
phs = newphs;
vector<int> quer = phs;
for (auto &x : quer)
x++;
for (int i = ind; i < min(ind + 8, (int)rs.size()); i++) {
for (int j = 0; j < (1 << (i - ind)); j++) {
quer.push_back(rs[i] + 1);
}
}
int val = query_sample(quer);
if (val == quer.size()) {
for (auto &x : phs)
ans[x] = 1;
return false;
}
for (int i = ind; i < min(ind + 8, (int)rs.size()); i++) {
if (val & (1 << (i - ind)))
ans[rs[i]] = 2;
else
ans[rs[i]] = 1;
}
ind += 8;
return true;
}
void test2(vector<int> &block, int tox, vector<int> &ans) {
vector<int> quer(1, tox + 1);
for (int i = 0; i < block.size(); i++) {
for (int j = 0; j < (1 << i); j++)
quer.push_back(block[i] + 1);
}
int val = query_sample(quer);
for (int i = 0; i < block.size(); i++) {
if (val & (1 << i)) {
ans[block[i]] = 2;
} else
ans[block[i]] = 1;
}
block.clear();
}
void determine_type(int n) {
vector<int> phs2;
vector<int> ans(n,
0); // 0: unknown, 1: reg, 2: strong, 3:tox, -1: R/S, -2: R/T
vector<int> rs;
for (int i = 0; i < n; i += 8) {
vector<int> quer;
for (int j = i; j < min(n, i + 8); j++)
for (int k = 0; k < (1 << (j - i)); k++)
quer.push_back(j + 1);
int val = query_sample(quer);
if (val == quer.size())
for (int j = i; j < min(n, i + 8); j++) {
ans[j] = -1;
rs.push_back(j);
}
else {
phs2.push_back(i);
for (int j = i; j < min(n, i + 8); j++) {
if (val & (1 << (j - i)))
ans[j] = 2;
else
ans[j] = -2;
}
}
}
int ind = 0;
for (int i = 0; i < phs2.size(); i++) {
vector<int> phs;
for (int j = phs2[i]; j < min(n, phs2[i] + 8); j++)
if (ans[j] == -2)
phs.push_back(j);
bool b = test(phs, ans, rs, ind);
while (b)
b = test(phs, ans, rs, ind);
}
int tox = 0;
for (int i = 0; i < n; i++)
if (ans[i] == 3)
tox = i;
vector<int> block;
for (int i = 0; i < n; i++) {
if (ans[i] <= 0)
block.push_back(i);
if (block.size() == 8)
test2(block, tox, ans);
}
if (!block.empty())
test2(block, tox, ans);
for (int i = 0; i < n; i++)
answer_type(i + 1, ans[i] == 1 ? 'R' : ans[i] == 2 ? 'S' : 'T');
}
