#include "toxic.h"
using namespace std;
#include <bits/stdc++.h>
// query_sample, answer_type
const int bitmax = 8;
void determine_type(int n){
vector<char> ans(n, 'R');
// find toxic
int lo = -1;
int hi = n + 1;
while (hi > lo + 1) {
int mid = (lo + hi) / 2;
vector<int> v; for (int i = 0; i <= mid; i++) v.push_back(i+1);
if (query_sample(v) < v.size()) hi = mid;
else lo = mid;
}
// hi is first toxic
int t = hi;
// cout << t << " first toxic\n";
int ptr = 0;
while (ptr < n) {
vector<int> query; query.push_back(t+1);
int add = 0;
for (int i = ptr; i < min(n, ptr + bitmax); i++) {
// add i, 2 ^ (ptr - i) tmes
for (int k = 0; k < ((int)1 << (i - ptr)); k++) query.push_back(i+1);
add++;
}
// cout << "Querying:\n";
// for (auto &x : query) cout << x << " ";
// cout << '\n';
int qv = query_sample(query);
// cout << qv << " returned\n";
// on bits are stronks
for (int i = 0; i < bitmax; i++) {
if (qv & ((int)1 << i)) {
// cout << ptr + i << " is S\n";
ans[ptr + i] = 'S';
}
}
ptr += add;
}
vector<int> inds; for (int i = 0; i < n; i++) {
if (ans[i] != 'S') {
inds.push_back(i);
// cout << i << " is in inds\n";
}
}
// for (auto &x : ans) cout << x;
// cout << '\n';
for (int i = 0; i < inds.size(); i += 4) {
vector<int> quer;
for (int j = i; j < min(i + 4, (int)inds.size()); j++) {
quer.push_back(inds[j]+1);
}
// cout << "Querying +4:\n";
// for (auto &x : quer) cout << x << " ";
// cout << '\n';
int qv = query_sample(quer);
// cout << qv << " returned\n";
if (qv < quer.size()) {
// toxic
int y = quer.size();
for (int j = 0; j < y; j++) {
int qv = query_sample({quer[j]});
if (!qv) {
// toxic
ans[quer[j] - 1] = 'T';
}
}
} else {
for (auto &x : quer) ans[x - 1] = 'R';
}
}
// cout << "Answering:\n";
// for (auto &x : ans) cout << x;
// cout << '\n';
for (int i = 0; i < n; i++) answer_type(i + 1, ans[i]);
}
