#include <bits/stdc++.h>
#include "Aoi.h"

using namespace std;

vector<int> operator * (vector<int> x, int y) {
    if (x.empty()) return {};
    vector<int> tres(x.size());
    for (int i = 0; i < (int)x.size(); ++i) {
        tres[i] += x[i] * y;
        if (i + 1 != (int)x.size()) {
            tres[i + 1] += tres[i] >> 10;
            tres[i] &= 1023;
        }
    }
    while (tres.back() >= 1024) {
        tres.push_back(tres.back() >> 10);
        tres[tres.size() - 2] &= 1023;
    }
    return tres;
}

vector<int> operator + (vector<int> x, int y) {
    if (!y) return x;
    if (x.empty()) {
        x = {0};
    }
    x[0] += y;
    int r = 0;
    while (r < (int)x.size() && x[r] >= 1024) {
        x[r] -= 1024;
        if (r == (int)x.size() - 1) x.push_back(0);
        ++x[r + 1];
    }
    return x;
}

string tr(vector<int> arr) {
    string res;
    for (int i = (int)arr.size() - 1; ~i; --i) {
        for (int j = 9; ~j; --j) {
            res += (char)(((arr[i] >> j) & 1) + '0');
        }
    }
    while (!res.empty() && res[0] == '0') {
        res = res.substr(1);
    }
    return res;
}

namespace Aoi {
    const int N = 1e4 + 5;

    vector< pair<int, long long> > G[N];
    long long dis[N];
    int pre[N];
    vector<int> T[N];
    int dep[N], clk[N];

    void dfs(int x) {
        for (auto v : T[x]) {
            dep[v] = dep[x] + 1, dfs(v), clk[x] = min(clk[x], clk[v]);
        }
    }
    
    int visit[N];

    void mark(int x) {
        while (x) {
            visit[x] = 1;
            x = pre[x];
        }
    }

    int getLst(int x) {
        while (x) {
            if (visit[x]) return x;
            x = pre[x];
        }
        return 0;
    }

    map< pair<int, int>, int> spe;

    int getId(int x) {
        while (x) {
            if (spe.count({x, pre[x]})) {
                return spe[{x, pre[x]}] + 1;
            }
            x = pre[x];
        }
        return 0;
    }

    string calc(vector< pair<int, int> > o) {
        vector<int> res;
        for (int i = (int)o.size() - 1; ~i; --i) {
            res = res * o[i].first + o[i].second;
        }
        return tr(res);
    }

    string aoi(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o) {
        for (int i = 0; i < m; ++i) {
            G[ox[i]].push_back({oy[i], oz[i]});
            G[oy[i]].push_back({ox[i], oz[i]});
        }
        for (int i = 1; i < n; ++i) {
            dis[i] = 1e18;
        }
        priority_queue< pair<long long, int> > pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            long long D = -pq.top().first;
            int x = pq.top().second;
            pq.pop();
            if (D != dis[x]) continue;
            for (auto [v, w] : G[x]) {
                long long nD = D + w;
                if (nD < dis[v] || (nD == dis[v] && x < pre[v])) {
                    if (nD != dis[v]) pq.push({-nD, v});
                    dis[v] = nD, pre[v] = x;
                }
            }
        }
        for (int i = 0; i < n; ++i) clk[i] = q;
        for (int i = 0; i < q; ++i) {
            clk[qr[i]] = min(clk[qr[i]], i);
        }
        for (int i = 1; i < n; ++i) {
            T[pre[i]].push_back(i);
        }
        dfs(0);
        vector< pair<int, int> > res;
        for (int i = 0; i < k; ++i) {
            if (dep[ox[o[i]]] > dep[oy[o[i]]]) swap(ox[o[i]], oy[o[i]]);
            res.push_back({q + 1, (pre[oy[o[i]]] == ox[o[i]] ? clk[oy[o[i]]] : q)});
            spe[{ox[o[i]], oy[o[i]]}] = spe[{oy[o[i]], ox[o[i]]}] = i;
        }
        mark(qr[0]);
        for (int i = 1; i < q; ++i) {
            res.push_back({k + 1, getId(getLst(qr[i]))});
            mark(qr[i]);
        }
        string ret = calc(res);
        assert((int)ret.size() <= 1349);
        return ret;
    }
}

string aoi(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o) {
    return Aoi::aoi(n, m, q, k, ox, oy, oz, qr, o);
}

#include <bits/stdc++.h>
#include "Bitaro.h"

using namespace std;

vector<int> operator / (vector<int> x, int y) {
    vector<int> tres(x.size());
    int now = 0;
    for (int i = (int)x.size() - 1; ~i; --i) { 
        now = (now << 10) + x[i];
        tres[i] = now / y;
        now %= y;
    }
    while (!tres.empty() && !tres.back()) {
        tres.pop_back();
    }
    return tres;
}

int operator % (vector<int> x, int y) {
    vector<int> tres(x.size());
    int now = 0;
    for (int i = (int)x.size() - 1; ~i; --i) { 
        now = (now << 10) + x[i];
        tres[i] = now / y;
        now %= y;
    }
    return now;
}

vector<int> parse(string S) {
    while (S.size() % 10) S = "0" + S;
    vector<int> res(S.size() / 10);
    for (int i = 0; i < (int)S.size(); i += 10) {
        for (int j = 0; j < 10; ++j) {
            res[(int)S.size() / 10 - 1 - i / 10] += (S[i + j] - '0') << (9 - j);
        }
    }
    return res;
}

namespace Bitaro {
    const int N = 1e4 + 5;

    vector<int> apd[N];
    int pre[N], det[N], dep[N], usd[N << 1];
    vector< tuple<int, int, long long> > E;
    long long dis[N];
    vector< pair<int, int> > ts;
    vector< pair<int, long long> > G[N];

    vector<int> process(int n, vector<int> imp, int id) {
        for (int i = 0; i < n; ++i) {
            G[i].clear();
            dis[i] = (i == 0 ? 0 : 1e18), pre[i] = 0;
        }
        for (auto [x, y, z] : E) {
            G[x].push_back({y, z});
            G[y].push_back({x, z});
        }
        for (auto x : imp) {
            G[ts[x].first].push_back({ts[x].second, 1});
            G[ts[x].second].push_back({ts[x].first, 1});
        }
        priority_queue< pair<long long, int> > pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            long long D = -pq.top().first;
            int x = pq.top().second;
            pq.pop();
            if (D != dis[x]) continue;
            for (auto [v, w] : G[x]) {
                long long nD = D + w;
                if (nD < dis[v] || (nD == dis[v] && x < pre[v])) {
                    if (nD != dis[v]) pq.push({-nD, v});
                    dis[v] = nD, pre[v] = x;
                }
            }
        }
        vector<int> path = {id};
        int now = id;
        while (now) {
            path.push_back(pre[now]);
            now = pre[now];
        }
        reverse(path.begin(), path.end());
        for (int i = 1; i < (int)path.size(); ++i) {
            det[path[i]] = path[i - 1];
            dep[path[i]] = dep[path[i - 1]] + 1;
        }
        return path;
    }

    void bitaro(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o, string S) {
        vector<int> val = parse(S);
        map< pair<int, int>, int> zM;
        for (int i = 0; i < k; ++i) {
            int cl = val % (q + 1);
            val = val / (q + 1);
            apd[cl].push_back(i);
            zM[{ox[o[i]], oy[o[i]]}] = zM[{oy[o[i]], ox[o[i]]}] = i;
        }
        map< pair<int, int>, int> M;
        for (int i = 0; i < m; ++i) {
            M[{ox[i], oy[i]}] = M[{oy[i], ox[i]}] = i;
        }
        for (int i = 0; i < k; ++i) {
            usd[o[i]] = 1;
            ts.push_back({ox[o[i]], oy[o[i]]});
        }
        for (int i = 0; i < m; ++i) {
            if (!usd[i]) E.push_back({ox[i], oy[i], oz[i]});
        }
        for (int i = 0; i < q; ++i) {
            vector<int> imp;
            if (i) {
                int id = val % (k + 1);
                val = val / (k + 1);
                if (id) {
                    --id;
                    if (dep[ox[o[id]]] < dep[oy[o[id]]]) {
                        swap(ox[o[id]], oy[o[id]]);
                    }
                    id = ox[o[id]];
                    while (id) {
                        if (usd[M[{id, det[id]}]]) {
                            imp.push_back(zM[{id, det[id]}]);
                        }
                        id = det[id];
                    }
                }
            }
            for (auto x : apd[i]) {
                imp.push_back(x);
            }
            vector<int> res = process(n, imp, qr[i]);
            vector<int> ids;
            for (int j = 0; j + 1 < (int)res.size(); ++j) {
                ids.push_back(M[{res[j], res[j + 1]}]);
            }
            answer(ids);
        }
    }
}

void bitaro(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o, string S) {
    Bitaro::bitaro(n, m, q, k, ox, oy, oz, qr, o, S);
}