#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(1);
void determine_type(int n){
vector<int> toxic;
vector<int> strong, regular;
vector<int> v(n); iota(v.begin(), v.end(), 1);
vector<int> v2;
int cnt=0;
while (v.size()){
shuffle(v.begin(), v.end(), rng);
vector<int> dead, vv;
while (vv.size()<8 && v.size()){
vv.push_back(v.back());
v.pop_back();
}
vector<int> query;
for (int j=0; j<(int)vv.size(); ++j){
for (int k=0; k<(1<<j); ++k) query.push_back(vv[j]);
}
int t=query.size();
if (cnt!=30){
t=query_sample(query);
}
if (t==((1<<(int)vv.size())-1)){
v2.insert(v2.end(), vv.begin(), vv.end());
}else{
for (int j=0; j<(int)vv.size(); ++j) if (t>>j&1) strong.push_back(vv[j]); else dead.push_back(vv[j]);
vv.clear();
int l=0, r=dead.size()-2;
while (l<=r){
int mid=(l+r)>>1;
query=vector<int>(dead.begin(), dead.begin()+mid+1);
while ((int)vv.size()<8 && v2.size()) vv.push_back(v2.back()), v2.pop_back();
for (int k=0; k<(int)vv.size(); ++k){
for (int _=0; _<(1<<k); ++_) query.push_back(vv[k]);
}
int tmp=query.size();
if (cnt!=30){
tmp=query_sample(query);
}
if (tmp!=(int)query.size()){
for (int k=0; k<(int)vv.size(); ++k) if (tmp>>k&1) strong.push_back(vv[k]); else regular.push_back(vv[k]);
vv.clear();
r=mid-1;
}else l=mid+1;
}
for (int j=0; j<l; ++j) regular.push_back(dead[j]);
toxic.push_back(dead[l]);
dead.erase(dead.begin(), dead.begin()+l+1);
++cnt;
if (vv.size()) v2.insert(v2.end(), vv.begin(), vv.end());
v.insert(v.end(), dead.begin(), dead.end());
}
}
v=v2;
while (v.size()){
shuffle(v.begin(), v.end(), rng);
vector<int> vv;
while (vv.size()<8 && v.size()){
vv.push_back(v.back());
v.pop_back();
}
vector<int> query{toxic[0]};
for (int k=0; k<(int)vv.size(); ++k){
for (int l=0; l<(1<<k); ++l) query.push_back(vv[k]);
}
int t=query_sample(query);
for (int k=0; k<(int)vv.size(); ++k) if (t>>k&1) strong.push_back(vv[k]); else regular.push_back(vv[k]);
}
for (int i:regular) answer_type(i, 'R');
for (int i:strong) answer_type(i, 'S');
for (int i:toxic) answer_type(i, 'T');
}
