#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;
vector<vector<int>> vrt;
auto query8=[&](int l, int r){
vector<int> v;
for (int i=l; i<=r; ++i){
int j=1<<(i-l);
while (j--) v.push_back(i);
}
int x=fake_query_sample(v);
if (x==(int)v.size()){
for (int i=l; i<=r; ++i) vsr.push_back(i);
}else{
vrt.emplace_back();
for (int i=l; i<=r; ++i){
if (x>>(i-l)&1){
answer[i]='S';
}else{
vrt.back().push_back(i);
}
}
}
};
auto query8_2=[&](int l, int r){
vector<int> v=vrt[0];
for (int i=l; i<=r; ++i){
int j=1<<(i-l);
while (j--) v.push_back(vsr[i]);
}
int x=fake_query_sample(v);
for (int i=l; i<=r; ++i){
if (x>>(i-l)&1){
answer[vsr[i]]='S';
}
}
};
for (int i=1; i<=n; i+=8) query8(i, min(n, i+7));
for (int i=0; i<(int)vsr.size(); i+=8) query8_2(i, min((int)vsr.size()-1, i+7));
for (auto &i:vrt){
do{
int l=1, r=(int)i.size()-1;
while (l<=r){
int mid=(l+r)>>1;
if (fake_query_sample(vector<int>(i.begin(), i.begin()+mid))) l=mid+1;
else r=mid-1;
}
answer[i[r]]='T';
i.erase(i.begin(), i.begin()+l);
}while (i.size() && !fake_query_sample(vector<int>(i.begin(), i.end())));
}
for (int i=1; i<=n; ++i) fake_answer_type(i, answer[i]);
}
