#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(69420);
void determine_type(int n){
vector<int> ct(n*4, -1), cr(n*4, -1), csr(n*4, -1), cs(n*4, -1);
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);
};
int id_t=0;
{
int l=1, r=n-1;
while (l<=r){
int mid=(l+r)>>1;
if (query(1, mid)!=mid) r=mid-1;
else l=mid+1;
}
id_t=l;
}
auto query8=[&](int l, int r){
vector<int> v{id_t};
for (int i=l; i<=r; ++i){
int j=1<<(i-l);
while (j--) v.push_back(i);
}
int x=fake_query_sample(v);
for (int i=l; i<=r; ++i){
if (x>>(i-l)&1){
answer[i]='S';
}
}
};
for (int i=1; i<=n; i+=8) query8(i, min(n, i+7));
vector<int> idx;
for (int i=1; i<=n; ++i) if (answer[i]=='R') idx.push_back(i);
while (idx.size()){
int sz=min(8, (int)idx.size());
vector<int> v(idx.begin(), idx.begin()+sz);
if (fake_query_sample(v)==v.size()){
idx.erase(idx.begin(), idx.begin()+sz);
continue;
}
int l=1, r=7;
while (l<=r){
int mid=(l+r)>>1;
if (fake_query_sample(vector<int>(idx.begin(), idx.begin()+mid))==mid) l=mid+1;
else r=mid-1;
}
answer[idx[r]]='T';
idx.erase(idx.begin(), idx.begin()+l);
}
for (int i=1; i<=n; ++i) fake_answer_type(i, answer[i]);
}
