#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
char type[301];
vector<int> v;
vector<int> pro;
vector<int> trans;
vector<vector<int>> segregate(vector<int> v, int n, int l){
vector<vector<int>> ans;
int cont = 0;
for(int i = 0; i < n ; i++){
if(cont == v.size()) break;
vector<int> temp;
for(int j = 0; j < l; j++){
if(cont == v.size()) break;
temp.push_back(v[cont]);
cont++;
}
ans.push_back(temp);
}
return ans;
}
int fquery(vector<int> v){
for(int i = 0; i < v.size(); i++){
v[i] = trans[v[i]];
}
return query_sample(v);
}
int squery(vector<int> v){
vector<int> sas;
vector<int> ind;
int sise = v.size();
int two = 1;
while(!pro.empty() && v.size() + two <= 300){
//printf("%d %d %d\n",pro.size(),fquery(v),v.size());
if(type[pro.back()] != 0){
pro.pop_back();
continue;
}
sas.push_back(two);
two *= 2;
ind.push_back(pro.back());
pro.pop_back();
for(int i = 0; i < sas.back(); i++){
v.push_back(ind.back());
}
}
int num = fquery(v);
if(num != v.size()){
while(!ind.empty()){
if(num >= sas.back()){
num -= sas.back();
type[ind.back()] = 'S';
}
else{
type[ind.back()] = 'R';
}
sas.pop_back();
ind.pop_back();
}
}
else{
for(int j : ind) pro.push_back(j);
return sise;
}
return num;
}
int oquery(vector<int> v){
vector<int> sas;
vector<int> ind;
int sise = v.size();
while(!pro.empty() && v.size() + v.size() <= 300){
//printf("%d %d %d\n",pro.size(),fquery(v),v.size());
if(type[pro.back()] != 0){
pro.pop_back();
continue;
}
sas.push_back(v.size());
ind.push_back(pro.back());
pro.pop_back();
for(int i = 0; i < sas.back(); i++){
v.push_back(ind.back());
}
}
int num = fquery(v);
if(num != v.size()){
while(!ind.empty()){
if(num >= sas.back()){
num -= sas.back();
type[ind.back()] = 'S';
}
else{
type[ind.back()] = 'R';
}
sas.pop_back();
ind.pop_back();
}
}
else{
for(int j : ind) pro.push_back(j);
return sise;
}
return num;
}
int iquery(vector<int> v){
vector<int> ind;
vector<int> sas;
int num = 0;
int N = v.size();
int sise = N;
for(int i = 1; i < N; i++){
int cont = (N-i);
for(int j = 0; j < i; j++){
cont = cont * 2 + 1;
}
if( cont > 300){
break;
}
num = i;
}
ind.push_back(v[0]);
sas.push_back(1);
for(int i = 0; i < num; i++){
ind.push_back(v.back());
v.pop_back();
}
for(int i = 1; i <= num; i++){
sas.push_back(v.size() + 1);
for(int j = 0; j < sas.back(); j++){
v.push_back(ind[i]);
}
}
num = oquery(v);
if(num != v.size()){
while(!ind.empty()){
if(num >= sas.back()){
num -= sas.back();
type[ind.back()] = 'S';
}
else{
type[ind.back()] = 'R';
}
sas.pop_back();
ind.pop_back();
}
return 0;
}
else{
return sise;
}
}
void findtoxicsub(vector<int> ve, int t){
/*if(squery(ve) == ve.size()){
for(int i : ve){
pro.push_back(i);
}
return;
}*/
if(ve.size() == 1){
if(squery(ve) == 0) type[ve[0]] = 'T';
return;
}
if(t > ve.size()){
t = ve.size();
}
int past = ve.size();
int num = (ve.size() + 1)/2 ;
int two = 1;
while(num >= t && num > 1){
two = two * 2;
past = num;
num = (num + 1)/2;
}
vector<vector<int>> pros = segregate(ve,past,two);
vector<vector<int>> next;
vector<int> ukown;
for(int i = 0; i < pros.size(); i++){
if(squery(pros[i]) != pros[i].size()){
next.push_back(pros[i]);
}
else{
for(int j : pros[i]){
pro.push_back(j);
}
}
}
while(next.size() != 0){
swap(pros,next);
next.clear();
for(int i = 0; i < pros.size(); i++){
vector<int> temp;
for(int j: pros[i]){
if(type[j] != 'S') temp.push_back(j);
}
pros[i] = temp;
temp.clear();
if(pros[i].size() == 0){
t++;
t--;
}
else if(pros[i].size() == 1){
t--;
type[pros[i][0]] = 'T';
}
else{
for(int j = 0; j < pros[i].size()/2 ; j++){
temp.push_back(pros[i][j]);
}
if(squery(temp) == temp.size()){
for(int i : temp){
pro.push_back(i);
}
temp.clear();
for(int j = pros[i].size()/2; j < pros[i].size(); j++){
temp.push_back(pros[i][j]);
}
next.push_back(temp);
}
else{
next.push_back(temp);
for(int j = pros[i].size()/2; j < pros[i].size(); j++){
ukown.push_back(pros[i][j]);
}
}
}
}
}
if(!ukown.empty()) findtoxicsub(ukown,t);
}
void findtoxic(vector<int> ve, int t){
int past = ve.size();
int num = (ve.size() + 1)/2 ;
int two = 1;
while(num >= t && num > 1){
two = two * 2;
past = num;
num = (num + 1)/2;
}
vector<vector<int>> pros = segregate(ve,past,two);
vector<vector<int>> next;
vector<int> ukown;
for(int i = 0; i < pros.size(); i++){
if(iquery(pros[i]) != pros[i].size()){
next.push_back(pros[i]);
}
else{
for(int j : pros[i]){
pro.push_back(j);
}
}
}
while(next.size() != 0){
swap(pros,next);
next.clear();
for(int i = 0; i < pros.size(); i++){
vector<int> temp;
for(int j: pros[i]){
if(type[j] != 'S') temp.push_back(j);
}
pros[i] = temp;
temp.clear();
if(pros[i].size() == 0){
t++;
t--;
}
else if(pros[i].size() == 1){
t--;
type[pros[i][0]] = 'T';
}
else{
for(int j = 0; j < pros[i].size()/2 ; j++){
temp.push_back(pros[i][j]);
}
if(squery(temp) == temp.size()){
for(int i : temp){
pro.push_back(i);
}
temp.clear();
for(int j = pros[i].size()/2; j < pros[i].size(); j++){
temp.push_back(pros[i][j]);
}
next.push_back(temp);
}
else{
next.push_back(temp);
for(int j = pros[i].size()/2; j < pros[i].size(); j++){
ukown.push_back(pros[i][j]);
}
}
}
}
}
if(!ukown.empty()) findtoxicsub(ukown,t);
}
void determine_type(int n){
v.clear();
trans.clear();
trans.push_back(0);
for(int i = 1; i <= n; i++){
type[i] = 0;
v.push_back(i);
trans.push_back(i);
}
random_shuffle ( trans.begin() + 1, trans.end());
random_shuffle ( trans.begin() + 1, trans.end());
random_shuffle ( trans.begin() + 1, trans.end());
pro.clear();
findtoxic(v,30);
int p;
for(int i = 1; i <= n; i++){
if(type[i] == 'T'){
p = i;
}
}
v.clear();
while(!pro.empty()){
if(type[pro.back()] != 0){
pro.pop_back();
}
squery(vector<int>{p});
}
for(int i = 1; i <= n; i++){
answer_type(trans[i], type[i]);
}
}
