#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fr first
#define se second
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int cnt = 0;
vector<int> gRange(int l, int r) {
vector<int> a;
for (int i = l; i <= r; i++) a.push_back(i);
return a;
}
bool good(int l, int r) {
return (query_sample(gRange(l, r)) == (r - l + 1));
}
vector<int> toxics;
void doIt(int l, int r) {
if (l == r) {
toxics.push_back(l);
return;
}
int m = (l + r)/2;
vector<pii> ra = {{l, m}, {m + 1, r}};
shuffle(ra.begin(), ra.end(), rng);
cnt++;
if (good(ra[0].fr, ra[0].se)) {
doIt(ra[1].fr, ra[1].se);
// ok
} else {
cnt++;
doIt(ra[0].fr, ra[0].se);
if (!good(ra[1].fr, ra[1].se)) doIt(ra[1].fr, ra[1].se);;
}
}
void determine_type(int n) {
cnt = 0;
toxics.clear();
doIt(1, n);
vector<int> tx(301);
for (auto u : toxics) {
tx[u] = 1;
answer_type(u, 'T');
}
vector<int> test;
for (int i = 1; i <= n; i++) {
if (!tx[i]) test.push_back(i);
}
while (!test.empty()) {
vector<int> curr;
while (!test.empty() && (((int) curr.size()) < 8)) {
curr.push_back(test.back());
test.pop_back();
}
vector<int> batch = {toxics[0]};
for (int i = 0; i < ((int) curr.size()); i++) {
int qtd = (1 << i);
while (qtd--) batch.push_back(curr[i]);
}
int r = query_sample(batch);
for (int i = 0; i < ((int) curr.size()); i++) {
if (r & (1 << i)) {
answer_type(curr[i], 'S');
} else {
answer_type(curr[i], 'R');
}
}
}
return;
}
