#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
void determine_type(int n){
vector<int> ct(n*4, -1), cr(n*4, -1), ctr(n*4, -1), cs(n*4, -1);
auto query=[&](int l, int r) -> int {
vector<int> v(r-l+1);
iota(v.begin(), v.end(), l);
return 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 query_t=[&](int l, int r) -> int {
vector<int> v(r-l+1);
iota(v.begin(), v.end(), l);
if (id_t<l || r<id_t){
v.push_back(id_t);
}
return query_sample(v);
};
auto dnc_t=[&](auto &&self, int k, int l, int r) -> void {
int c=query(l, r);
if (c){
for (int i=l; i<=r; ++i) answer_type(i, 'R');
return;
}
if (l==r){
answer_type(l, 'T');
return;
}
int mid=(l+r)>>1;
self(self, k<<1, l, mid);
self(self, k<<1|1, mid+1, r);
};
auto dnc=[&](auto &&self, int k, int l, int r) -> void {
if (cs[k]==-1) cs[k]=query_t(l, r);
if (cs[k]==r-l+1){
for (int i=l; i<=r; ++i) answer_type(i, 'S');
return;
}
if (cs[k]==0) return dnc_t(dnc_t, k, l, r);
assert(l!=r);
int mid=(l+r)>>1;
self(self, k<<1, l, mid);
cs[k<<1|1]=cs[k]-cs[k<<1];
self(self, k<<1|1, mid+1, r);
};
dnc(dnc, 1, 1, n);
}
