#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 305;
const int SIZE = 8;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>sr, tr;
char ans[lim];
bitset<lim>not_toxic;
bool is_toxic(vector<int>cand){
vector<int>norm;
while(!sr.empty() && norm.size() < SIZE){
norm.push_back(sr.back());
sr.pop_back();
}
vector<int>ask = cand;
for(int i = 0; i < norm.size(); i++){
for(int j = 1 << i; j > 0; j--){
ask.push_back(norm[i]);
}
}
int x = query_sample(ask);
if(x == ask.size()){
for(int& i : norm){
sr.push_back(i);
not_toxic[i] = true;
}
for(int& i : cand){
ans[i] = 'R';
not_toxic[i] = true;
}
return false;
}
for(int i = 0; i < norm.size(); i++){
ans[norm[i]] = (x >> i & 1) ? 'S' : 'R';
}
return true;
}
int find_toxic(vector<int>cand){
if(cand.size() == 1){
return cand[0];
}
int m = int(cand.size()) >> 1;
vector<int>left(cand.begin(), cand.begin() + m);
return !left.empty() && is_toxic(left) ? find_toxic(left) : find_toxic(vector<int>(cand.begin() + m, cand.end()));
}
void determine_type(int n){
vector<int>ord(n);
iota(ord.begin(), ord.end(), 1);
shuffle(ord.begin(), ord.end(), rng);
sr.clear();
tr.clear();
not_toxic.reset();
fill(ans + 1, ans + n + 1, '#');
for(int i = 0; i < ord.size(); i += SIZE){
vector<int>ask;
for(int j = 0; j < SIZE && i + j < ord.size(); j++){
for(int k = 1 << j; k > 0; k--){
ask.push_back(ord[i + j]);
}
}
int x = query_sample(ask);
if(x == ask.size()){
for(int j = 0; j < SIZE && i + j < ord.size(); j++){
sr.push_back(ord[i + j]);
}
}
else{
vector<int>cand;
for(int j = 0; j < SIZE && i + j < ord.size(); j++){
if(x >> j & 1){
ans[ord[i + j]] = 'S';
}
else{
cand.push_back(ord[i + j]);
}
}
ans[x = find_toxic(cand)] = 'T';
for(int& j : cand){
if(j != x && !not_toxic[j]){
tr.push_back(j);
}
}
}
}
while(!tr.empty()){
vector<int>cand;
while(!tr.empty() && cand.size() < SIZE){
cand.push_back(tr.back());
tr.pop_back();
}
if(is_toxic(cand)){
int x = find_toxic(cand);
ans[x] = 'T';
for(int& i : cand){
if(i != x && !not_toxic[i]){
tr.push_back(i);
}
}
}
else{
for(int& i : cand){
ans[i] = 'R';
}
}
}
int toxic = find(ans + 1, ans + n + 1, 'T') - ans;
for(int i = 0; i < sr.size(); i += SIZE){
vector<int>ask(1, toxic);
for(int j = 0; j < SIZE && i + j < sr.size(); j++){
for(int k = 1 << j; k > 0; k--){
ask.push_back(sr[i + j]);
}
}
for(int j = 0, x = query_sample(ask); j < SIZE && i + j < sr.size(); j++){
ans[sr[i + j]] = (x >> j & 1) ? 'S' : 'R';
}
}
for(int i = 1; i <= n; i++){
answer_type(i, ans[i]);
}
}
