1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

// City IDs: 1..N (up to 2000), sent as 0..N-1 → 11 bits (2^11=2048 > 1999)
// Costs: 1..500, sent as 0..499 → 9 bits (2^9=512 > 499)
const int CITY_BITS = 11;
const int COST_BITS = 9;

void sendBit(int b) {
    cout << "+ " << b << "\n";
    cout.flush();
}

int recvBit() {
    cout << "?\n";
    cout.flush();
    int b;
    cin >> b;
    return b;
}

// Send val (MSB first) using 'bits' bits
void sendInt(int val, int bits) {
    for (int i = bits - 1; i >= 0; i--)
        sendBit((val >> i) & 1);
}

// Receive an integer encoded in 'bits' bits (MSB first)
int recvInt(int bits) {
    int val = 0;
    for (int i = bits - 1; i >= 0; i--)
        val |= (recvBit() << i);
    return val;
}

// Algosia: knows the bus network, wants shortest paths from city 1.
// Protocol per finalized city u:
//   Algosia → Bajtek: u-1 in CITY_BITS bits
//   Bajtek  → Algosia: for each train edge (u,v,c) where v is not yet finalized:
//               1 bit (has_more=1), then v-1 in CITY_BITS bits, then c-1 in COST_BITS bits
//             followed by 1 bit (has_more=0, end)
void solveAlgosia() {
    int N, A;
    cin >> N >> A;

    vector<vector<pair<int,int>>> bus(N + 1);
    for (int i = 0; i < A; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        bus[u].push_back({v, c});
        bus[v].push_back({u, c});
    }

    const long long INF = 1e18;
    vector<long long> dist(N + 1, INF);
    dist[1] = 0;
    // min-heap: (distance, city)
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    pq.push({0, 1});
    vector<bool> fin(N + 1, false);
    int cnt = 0;

    while (cnt < N && !pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (fin[u]) continue;
        fin[u] = true;
        cnt++;

        // Notify Bajtek which city we just finalized
        sendInt(u - 1, CITY_BITS);

        // Receive train edges from Bajtek (from u to non-finalized cities)
        while (true) {
            if (!recvBit()) break;              // has_more == 0 → done
            int v = recvInt(CITY_BITS) + 1;
            int c = recvInt(COST_BITS) + 1;
            if (d + c < dist[v]) {
                dist[v] = d + c;
                pq.push({dist[v], v});
            }
        }

        // Relax bus edges from u
        for (auto [v, c] : bus[u]) {
            if (d + c < dist[v]) {
                dist[v] = d + c;
                pq.push({dist[v], v});
            }
        }
    }

    // Output shortest distances from city 1 to all cities
    cout << "!";
    for (int i = 1; i <= N; i++)
        cout << " " << dist[i];
    cout << "\n";
    cout.flush();
}

// Bajtek: knows the train network.
// Receives finalized city IDs from Algosia one by one (N total).
// For each finalized city u, sends all train edges from u to not-yet-finalized cities.
void solveBajtek() {
    int N, B;
    cin >> N >> B;

    vector<vector<pair<int,int>>> train(N + 1);
    for (int i = 0; i < B; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        train[u].push_back({v, c});
        train[v].push_back({u, c});
    }

    vector<bool> fin(N + 1, false);

    for (int i = 0; i < N; i++) {
        int u = recvInt(CITY_BITS) + 1;
        fin[u] = true;

        // Send train edges from u to non-finalized cities
        for (auto [v, c] : train[u]) {
            if (!fin[v]) {
                sendBit(1);                     // has_more = 1
                sendInt(v - 1, CITY_BITS);
                sendInt(c - 1, COST_BITS);
            }
        }
        sendBit(0);                             // has_more = 0 → end of edges for u
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string role;
    cin >> role;

    if (role == "Algosia") solveAlgosia();
    else solveBajtek();

    return 0;
}