#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
int t, x;
vector <int> ord, non, g, h, c, q;
vector <vector<int>> sus;
bool tri() {
g.clear();
q = c;
while (g.size() < 8 && !non.empty()) {
g.push_back(non.back());
non.pop_back();
}
for (int i=0;i<g.size();i++) {
for (int j=0;j<(1<<i);j++) {
q.push_back(g[i]);
}
}
x = query_sample(q);
if (x == q.size()) {
for (int i : c) {
answer_type(i, 'R');
}
for (int i : g) {
non.push_back(i);
}
return 0;
}
for (int i=0;i<g.size();i++) {
if ((x>>i)&1) {
answer_type(g[i], 'S');
}
else {
answer_type(g[i], 'R');
}
}
return 1;
}
void two() {
int l=0, r=h.size()-1;
while (l<r) {
int mid=(l+r)/2;
q.clear();
c.clear();
for (int i=l;i<=mid;i++) {
c.push_back(h[i]);
}
if (tri()) {
r = mid;
}
else {
l = mid+1;
}
}
answer_type(h[l], 'T');
t = h[l];
for (int i=l+1;i<h.size();i++) {
ord.push_back(h[i]);
}
}
void one() {
g.clear();
q.clear();
while (g.size() < 8 && !ord.empty()) {
g.push_back(ord.back());
ord.pop_back();
}
for (int i=0;i<g.size();i++) {
for (int j=0;j<(1<<i);j++) {
q.push_back(g[i]);
}
}
x = query_sample(q);
if (x == q.size()) {
for (int i : g) {
non.push_back(i);
}
}
else {
h.clear();
for (int i=0;i<g.size();i++) {
if ((x>>i)&1) {
answer_type(g[i], 'S');
}
else {
h.push_back(g[i]);
}
}
sus.push_back(h);
}
}
void determine_type(int n) {
srand(time(NULL));
for (int i=1;i<=n;i++) {
ord.push_back(i);
swap(ord[rand()%i],ord[i-1]);
}
while (!ord.empty()) {
one();
}
while (!sus.empty()) {
for (auto x : sus) {
h = x;
two();
}
sus.clear();
while (!ord.empty()) {
c.clear();
while (c.size() < 8 && !ord.empty()) {
c.push_back(ord.back());
ord.pop_back();
}
if (tri()) {
sus.push_back(c);
}
}
}
c.clear();
c.push_back(t);
while (!non.empty()) {
tri();
}
}
