/* 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, y;
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;
void send(int ps, char c){
if(found[ps]) return;
found[ps] = 1;
answer_type(ps + 1, c);
}
void send(int ps, char c, char mm){
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()){
v.clear();
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;
if(query(get_vector_range(v, l, mid)) == mid - l + 1){
l = mid + 1;
}else{
res = mid;
r = mid - 1;
}
}
pos = res;
// cout << v[pos] << " toxic\n";
send(v[pos], 'T');
y = v[pos];
for(int j = 0; j < pos; ++j){
if(!found[v[j]]){
send(v[j], 'R', 'm');
}
}
for(int j = 0; j <= pos; ++j) v.erase(v.begin());
for(int j = 0; j < v.size(); ++j){
if(found[v[j]]){
v.erase(v.begin() + j);
--j;
}
}
return -1;
}
assert(false);
return -1;
}
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){
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)]);
}
vi V;
for(int i = 0; i < n; i++){
V.pb(C[i]);
if(V.size() == 8){
identify(V);
}
}
while(!V.empty()) identify(V);
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);
}
}
