#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(69420);
void determine_type(int n){
vector<int> mp(n+1);
iota(mp.begin(), mp.end(), 0);
shuffle(mp.begin()+1, mp.end(), rng);
vector<int> answer(n+1, 'R');
auto fake_query_sample=[&](vector<int> v) -> int {
for (int &i:v) i=mp[i];
return query_sample(v);
};
auto fake_answer_type=[&](int x, char c) -> void {
return answer_type(mp[x], c);
};
auto query=[&](int l, int r) -> int {
vector<int> v(r-l+1);
iota(v.begin(), v.end(), l);
return fake_query_sample(v);
};
vector<int> vsr;
int tid=0;
vector<int> v;
auto query8=[&](int sz){
vector<int> vv;
for (int i=0; i<sz; ++i){
int j=1<<i;
while (j--) vv.push_back(v[i]);
}
int x=fake_query_sample(vv);
if (x==(int)vv.size()){
for (int i=0; i<sz; ++i) vsr.push_back(v[i]);
}else{
vector<int> vrt;
for (int i=0; i<sz; ++i){
if (x>>i&1){
answer[v[i]]='S';
}else{
vrt.push_back(v[i]);
}
}
int l=1, r=(int)vrt.size()-1;
while (l<=r){
int mid=(l+r)>>1;
if (fake_query_sample(vector<int>(vrt.begin(), vrt.begin()+mid))) l=mid+1;
else r=mid-1;
}
answer[vrt[r]]='T';
tid=vrt[r];
vrt.erase(vrt.begin(), vrt.begin()+l);
v.insert(v.end(), vrt.begin(), vrt.end());
}
v.erase(v.begin(), v.begin()+sz);
};
auto query8_2=[&](int sz){
vector<int> vv={tid};
for (int i=0; i<sz; ++i){
int j=1<<i;
while (j--) vv.push_back(vsr[i]);
}
int x=fake_query_sample(vv);
for (int i=0; i<sz; ++i){
if (x>>i&1){
answer[vsr[i]]='S';
}
}
vsr.erase(vsr.begin(), vsr.begin()+sz);
};
v.resize(n);
iota(v.begin(), v.end(), 1);
while (v.size()) query8(min(8, (int)v.size()));
while (vsr.size()) query8_2(min(8, (int)vsr.size()));
for (int i=1; i<=n; ++i) fake_answer_type(i, answer[i]);
}
