#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void determine_type(int n){
int perm[n];
vector<int>ans(n+1,-1);
iota(perm , perm + n , 1);
shuffle(perm , perm + n , rng);
int toxic;
{
int l = 0 , r = n-1;
while(l < r){
int mid = (l + r) / 2;
vector<int>vec;
for(int j = l;j<=mid;j++)vec.push_back(perm[j]);
if(query_sample(vec) == mid-l+1){
l = mid+1;
}
else {
r = mid;
}
}
toxic = perm[l];
}
// eliminate the strong ones
for(int i = 0;i<n;i+=8){
vector<int>vec;
int bruh = 0;
for(int j = 0;j<8;j++){
if(i+j>=n)continue;
int tmp = 1 << j;
bruh += tmp;
while(tmp--)vec.push_back(perm[i+j]);
}
int cevap = query_sample(vec);
if(cevap == bruh){// S ve R lerden olusan grup
vec.push_back(toxic);
cevap = query_sample(vec);
for(int j = 0;j<8;j++){
if(i+j>=n)continue;
if(cevap & (1 << j))ans[perm[i+j]] = 2;
else ans[perm[i+j]] = 0;
}
}
else{// T S R
for(int j = 0;j<8;j++){
if(cevap & (1 << j))ans[perm[i+j]] = 2;
}
}
}
vector<int>v;
for(int i = 0;i<n;i++)
if(ans[perm[i]] == -1)
v.push_back(perm[i]);
shuffle(v.begin() , v.end() , rng);
int sayac = 0;
function<void(int,int)> dfs = [&](int l , int r){
if(l == r){
ans[v[l]] = 1;
return;
}
int mid = (l + r) / 2;
vector<int>vec1,vec2;
for(int i = l;i<=mid;i++)
vec1.push_back(v[i]);
for(int i = mid+1;i<=r;i++)
vec2.push_back(v[i]);
sayac += 2;
if(query_sample(vec1) == 0){
dfs(l,mid);
if(query_sample(vec2) == 0)dfs(mid+1,r);
}
else dfs(mid+1,r);
};
dfs(0,v.size()-1);
// cout << "sayac : " << sayac << endl;
for(int i = 1;i<=n;i++)
if(ans[i] == -1)
ans[i] = 0;
for(int i = 1;i<=n;i++){
if(ans[i] == 0){
answer_type(i,'R');
// cout << "R";
}
else if(ans[i] == 1){
answer_type(i,'T');
// cout << "T";
}
else {
answer_type(i,'S');
// cout << "S";
}
}
// cout << endl;
}
