/* Author : Mychecksdead */
#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rn(int l, int r){
return uniform_int_distribution<int>(l,r)(rng);
}
int qq;
int query(vi v){
vi u;
if(qq > 250){
assert(false);
}
++qq;
for(int x: v) u.pb(x+1);
return query_sample(u);
}
vi get_vector_range(vi v, int l, int r){
vi res;
for(int j = l; j <= r; ++j) res.pb(v[j]);
return res;
}
bitset<N> found;
vi bad;
void send(int ps, char c){
if(found[ps]) return;
found[ps] = 1;
answer_type(ps + 1, c);
}
int identify(vi v){ // there is certainly 1 in v
int n = v.size();
int pos = -1;
while(pos + 1 < n){
int l = pos + 1, r = n - 1, res = n - 1;
vi U;
for(int j = l; j <= r; ++j){
for(int i = 0; i < (1<<j); ++i) U.pb(v[j]);
}
// for(int x: U) cout << x << ' ';
int num = query(U);
// cout << U.size() << ' ' << toxic << '\n';
if(num == U.size()){
if(pos != -1){
for(int j = 0; j < v.size(); ++j){
if(!found[v[j]]){
send(v[j], 'R');
}
}
}
return pos == -1 ? -1 : v[pos];
}
for(int j = l; j <= r; ++j){
if((1<<j)&num) send(v[j], 'S');
}
// if(query(get_vector_range(v, l, r)) == r - l + 1) return (pos == -1 ? -1 : v[pos]);
r = n - 2;
res = n - 1;
while(l <= r){
int mid = l+r>>1;
vi bad_5, bad5;
int e = 8, ee = 0;
while(bad.size() && bad_5.size()<5){
for(int i = 0; i < e; ++i) bad_5.pb(bad.back());
bad5.pb(bad.back());
bad.pop_back();
e *= 2;
++ee;
}
vi ragne = get_vector_range(v, l, mid);
for(int x: bad_5) ragne.pb(x);
int num = query(ragne);
if(num == ragne.size()){
l = mid + 1;
for(int x: bad5) bad.pb(x);
}else{
for(int i = 0; i < ee; ++i){
if((num&(1<<(i+3)))){
send(bad5[i], 'S');
}else{
send(bad5[i], 'R');
}
}
res = mid;
r = mid - 1;
}
}
pos = res;
// cout << v[pos] << " toxic\n";
send(v[pos], 'T');
}
if(pos != -1){
for(int j = 0; j < v.size(); ++j){
if(!found[v[j]]){
send(v[j], 'R');
}
}
}
if(pos==-1) return -1;
return v[pos];
}
void identify_stronq(vi v, int toxic){
vi U;
U.pb(toxic);
for(int j = 0; j < v.size(); ++j){
for(int i = 0; i < (1<<j); ++i) U.pb(v[j]);
}
// for(int x: U) cout << x << ' ';
int num = query(U);
// cout << U.size() << ' ' << toxic << '\n';
for(int j = 0; j < v.size(); ++j){
if((1<<j)&num) send(v[j], 'S');
else send(v[j], 'R');
}
}
void determine_type(int n){
int y = 0;
qq = 0;
found = 0;
vi C;
for(int i = 0; i < n; ++i){
C.pb(i);
swap(C[i], C[rn(0,i)]);
}
bad.clear();
for(int i = 0; i < n; i += 8){
vi v;
for(int j = i; j < min(i+8, n); ++j) v.pb(C[j]);
int x = identify(v);
if(x != -1){
y = x;
}else{
for(int f: v) bad.pb(f);
}
}
vi A;
for(int i = 0; i < n; ++i) if(!found[i]) A.pb(i);
for(int i = 0; i < A.size(); i += 8){
vi v;
for(int j = i; j < min(i + 8, int(A.size())); ++j) v.pb(A[j]);
identify_stronq(v, y);
}
}
