#include "toxic.h"
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
namespace {
std::vector<int> ans;
void send(int p, char c) {
if (ans[p]) {
return;
}
ans[p] = true;
debug(p, c);
answer_type(p, c);
}
std::random_device rd;
std::mt19937 rng(rd());
};
void determine_type(int n){
// std::vector<int> v;
// v.push_back(1);
// int qvalue = query_sample(v);
// answer_type(1,'T');
debug("NEW TC: ", n);
ans.assign(n + 1, 0);
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 1);
std::shuffle(ord.begin(), ord.end(), rng);
std::vector<int> sr, tr, notsure;
for (int i = 0; i < n; ++i) {
notsure.emplace_back(ord[i]);
}
int toxic = -1;
auto identify = [&](auto&& self, std::vector<int> v) -> void {
debug("NS", v);
if (v.size() == 1) {
toxic = v[0];
send(v[0], 'T');
return;
}
int m = int(v.size());
std::vector<int> askv;
std::vector<int> lhs(v.begin(), v.begin() + m / 2);
std::vector<int> rhs(v.begin() + m / 2, v.end());
int a = std::min(int(sr.size()), 8 - m / 2);
for (int i = 0; i < m / 2; ++i) {
for (int j = 0; j < (1 << i); ++j) {
askv.emplace_back(v[i]);
}
}
for (int i = 0; i < a; ++i) {
debug("sr", sr[i]);
for (int j = 0; j < (1 << (m / 2 + i)); ++j) {
askv.emplace_back(sr[i]);
}
}
int qval = query_sample(askv);
debug(qval);
if (qval == (1 << (m / 2 + a)) - 1) {
for (int i = 0; i < m / 2; ++i) {
send(v[i], 'R');
}
self(self, rhs);
} else {
for (int i = 0; i < a; ++i) {
if (qval >> (m / 2 + i) & 1) {
send(sr[0], 'S');
} else {
send(sr[0], 'R');
}
sr.erase(sr.begin());
}
for (int i = m / 2; i < m; ++i) {
tr.emplace_back(v[i]);
}
self(self, lhs);
}
};
auto identifytr = [&](auto&& self, std::vector<int> v) -> void {
debug("TR", v);
if (v.size() == 1) {
std::vector<int> askv;
int a = std::min(int(sr.size()), 8);
askv.emplace_back(v[0]);
for (int i = 0; i < a; ++i) {
for (int j = 0; j < (1 << i); ++j) {
askv.emplace_back(sr[i]);
}
}
int qval = query_sample(askv);
debug(qval);
if (qval == (1 << a)) {
send(v[0], 'R');
} else {
send(v[0], 'T');
for (int i = 0; i < a; ++i) {
if (qval >> i & 1) {
send(sr[0], 'S');
} else {
send(sr[0], 'R');
}
sr.erase(sr.begin());
}
}
debug("gg");
return;
}
int m = int(v.size());
std::vector<int> askv;
std::vector<int> lhs(v.begin(), v.begin() + m / 2);
std::vector<int> rhs(v.begin() + m / 2, v.end());
int a = std::min(int(sr.size()), 8 - m / 2);
for (int i = 0; i < m / 2; ++i) {
for (int j = 0; j < (1 << i); ++j) {
askv.emplace_back(v[i]);
}
}
for (int i = 0; i < a; ++i) {
debug(sr[i]);
for (int j = 0; j < (1 << (m / 2 + i)); ++j) {
askv.emplace_back(sr[i]);
}
}
int qval = query_sample(askv);
debug(qval);
if (qval == (1 << (m / 2 + a)) - 1) {
for (int i = 0; i < m / 2; ++i) {
send(v[i], 'R');
}
self(self, rhs);
} else {
for (int i = 0; i < a; ++i) {
if (qval >> (m / 2 + i) & 1) {
send(sr[0], 'S');
} else {
send(sr[0], 'R');
}
sr.erase(sr.begin());
}
for (int i = m / 2; i < m; ++i) {
tr.emplace_back(v[i]);
}
self(self, lhs);
}
};
while (!notsure.empty()) {
int m = std::min(7, int(notsure.size()));
std::vector<int> get(m);
for (int i = 0; i < m; ++i) {
get[i] = notsure.back();
notsure.pop_back();
}
int a = std::min(int(sr.size()), 8 - m);
debug(get);
std::vector<int> v;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < (1 << i); ++j) {
v.emplace_back(get[i]);
}
}
for (int i = 0; i < a; ++i) {
for (int j = 0; j < (1 << (m + i)); ++j) {
v.emplace_back(sr[i]);
}
}
int qval = query_sample(v);
debug(qval, v.size());
if (qval == (1 << (m + a)) - 1) {
for (int i = 0; i < m; ++i) {
sr.emplace_back(get[i]);
}
} else {
std::vector<int> oth;
for (int i = 0; i < m; ++i) {
if (qval >> i & 1) {
send(get[i], 'S');
} else {
oth.emplace_back(get[i]);
}
}
for (int i = 0; i < a; ++i) {
if (qval >> (m + i) & 1) {
send(sr[0], 'S');
} else {
send(sr[0], 'R');
}
sr.erase(sr.begin());
}
identify(identify, oth);
}
}
debug("ok");
assert(toxic != -1);
while (!tr.empty()) {
int m = std::min(8, int(tr.size()));
std::vector<int> get(m);
for (int i = 0; i < m; ++i) {
get[i] = tr.back();
tr.pop_back();
}
int a = std::min(int(sr.size()), 8 - m);
std::vector<int> askv;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < (1 << i); ++j) {
askv.emplace_back(get[i]);
}
}
for (int i = 0; i < a; ++i) {
for (int j = 0; j < (1 << (m + i)); ++j) {
askv.emplace_back(sr[i]);
}
}
int qval = query_sample(askv);
debug(get, qval);
if (qval == (1 << (m + a)) - 1) {
for (int i = 0; i < m; ++i) {
send(get[i], 'R');
}
} else {
std::vector<int> oth;
for (int i = 0; i < m; ++i) {
if (qval >> i & 1) {
send(get[i], 'S');
} else {
oth.emplace_back(get[i]);
}
}
for (int i = 0; i < a; ++i) {
if (qval >> (m + i) & 1) {
send(sr[0], 'S');
} else {
send(sr[0], 'R');
}
sr.erase(sr.begin());
}
identifytr(identifytr, oth);
}
}
while (!sr.empty()) {
int m = std::min(8, int(sr.size()));
std::vector<int> get(m);
for (int i = 0; i < m; ++i) {
get[i] = sr.back();
sr.pop_back();
}
std::vector<int> v;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < (1 << i); ++j) {
v.emplace_back(get[i]);
}
}
v.emplace_back(toxic);
int qval = query_sample(v);
for (int i = 0; i < m; ++i) {
if (qval >> i & 1) {
send(get[i], 'S');
} else {
send(get[i], 'R');
}
}
}
}
