Twisty Little Passages

#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
pair<int, int> input() {
    int room, pass;
    cin>>room>>pass;
    return {room, pass};
}
void operationWalk() {
    cout<<"W"<<endl;
}
void operationTeleport(int n) {
    cout<<"T "<<n<<endl;
}
vector<int> initVisOrder(int n) {
    vector<int> order;
    for(int i = 1; i <= n; i++)
        order.push_back(i);

    for(int i = n - 1; i > 0; i--) {
        int r = rand() % i;
        swap(order[r], order[i]);
    }
    return order;
}
string exactJustify(int n) {
    long long res = 0;
    auto [r, p] = input();
    res += p;
    for(int i = 0; i < n; i++) {
        if(i + 1 == r) continue;
        operationTeleport(i + 1);
        auto [room, pass] = input();
        res += pass;
    }
    return "E " + to_string(res / 2);
}
int pickRandom(vector<int>& order, unordered_set<int>& vis) {
    while(vis.count(order.back()))
        order.pop_back();
    return order.back();
}
string guessJustify(int n, int k) {
    unordered_set<int> vis;
    vector<int> visOrder = initVisOrder(n);

    vector<int> avg(n + 1), odd(n + 1);
    auto [r, p] = input();
    avg[r] = p;

    vis.insert(r);

    for(int i = 0; i < k / 2; i++) {
        operationWalk();
        auto [wr, wp] = input();
        odd[wr] = wp;
        avg[wr] = 0;
        vis.insert(wr);

        operationTeleport(pickRandom(visOrder, vis));
        auto [tr, tp] = input();
        avg[tr] = tp;
        vis.insert(tr);
    }

    if(k & 1) {
        operationWalk();
        auto [wr, wp] = input();
        odd[wr] = wp;
        avg[wr] = 0;
        vis.insert(wr);
    }

    long long res = 0;

    long long sum = 0, avgCnt = 0, oddSum = 0, oddCnt = 0;

    for(auto& pass : avg) {
        sum += pass;
        avgCnt += (pass > 0);
    }

    for(auto& pass : odd) {
        oddSum += pass;
        oddCnt += (pass > 0);
    }

    res = oddSum + (1.0 * sum / avgCnt) * (n - oddCnt);

    return "E " + to_string(res / 2);
}
string solve(int n, int k) {
    if(n - 1 <= k) {
        return exactJustify(n);
    } else {
        return guessJustify(n, k);
    }
}

int main() {
    srand((unsigned int)time(NULL));
    int tc;
    cin>>tc;
    for(int i = 1; i <= tc; i++) {
        int n,k;
        cin>>n>>k;
        cout<<solve(n,k)<<endl;
    }
    return 0;
}