ABC 416

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, L, R;
    cin >> N >> L >> R;
    L--, R--;
    string S;
    cin >> S;
    int ok = 1;
    for (int i = L; i <= R; i++) {
        if (S[i] != 'o') ok = 0;
    }
    yesno(ok);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int N = S.size();
    string T;
    T = S;
    rep(i, N) if (T[i] != '#') {
        T[i] = 'o';
    }

    rep(i, N) rep2(j, i + 1, N) {
        if (T[i] == 'o' && T[j] == 'o') {
            int has = 0;
            rep2(k, i + 1, j) if (T[k] == '#') has = 1;
            if (!has) T[j] = '.';
        }
    }

    cout << T << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K, X;
    cin >> N >> K >> X;
    vector<string> S(N);
    rep(i, N) cin >> S[i];

    vector<string> cand;
    int nk = intpow(N, K);
    rep(t, nk) {
        ll state = t;
        vint ids;
        rep(i, K) {
            ids.push_back(state % N);
            state /= N;
        }

        string s = "";
        for (int id : ids) s += S[id];
        cand.push_back(s);
    }
    sort(all(cand));
    cout << cand[X - 1] << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        ll N, M;
        cin >> N >> M;
        vll A(N), B(N);
        rep(i, N) {
            cin >> A[i];
        }
        rep(i, N) {
            cin >> B[i];
        }

        multiset<ll> sa, sb;
        rep(i, N) sa.insert(A[i]);
        rep(i, N) sb.insert(B[i]);

        sort(rall(A));

        ll ans = 0;
        for (ll a : A) {
            ll t = M - a;
            auto it = sb.lower_bound(t);
            if (it == sb.end()) it = prev(it);
            ll tmp = ((a + *it) % M);
            ans += tmp;
            sb.erase(it);
        }
        cout << ans << endl;
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;

    vvll dist(N + 1, vll(N + 1, INF));
    rep(i, N + 1) dist[i][i] = 0;
    rep(i, M) {
        ll u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        chmin(dist[u][v], c);
        chmin(dist[v][u], c);
    }

    ll K, T;
    cin >> K >> T;
    rep(i, K) {
        ll d;
        cin >> d;
        d--;
        dist[d][N] = T;
        dist[N][d] = 0;
    }

    auto warshallfloyd = [&]() -> void {
        rep(k, N + 1) rep(i, N + 1) rep(j, N + 1) {
            chmin(dist[i][j], dist[i][k] + dist[k][j]);
        }
    };

    auto Sum = [&]() -> ll {
        ll ret = 0;
        rep(i, N) rep(j, N) {
            if (dist[i][j] == INF) continue;
            ret += dist[i][j];
        }
        return ret;
    };

    warshallfloyd();

    int Q;
    cin >> Q;
    rep(i, Q) {
        int query_type;
        cin >> query_type;
        if (query_type == 1) {
            ll x, y, t;
            cin >> x >> y >> t;
            x--, y--;
            chmin(dist[x][y], t);
            chmin(dist[y][x], t);

            rep(i, N + 1) rep(j, N + 1) {
                chmin(dist[i][j], dist[i][y] + dist[y][x] + dist[x][j]);
            }
            rep(i, N + 1) rep(j, N + 1) {
                chmin(dist[i][j], dist[i][x] + dist[x][y] + dist[y][j]);
            }
        } else if (query_type == 2) {
            ll x;
            cin >> x;
            x--;
            dist[x][N] = T;
            dist[N][x] = 0;
            rep(i, N + 1) rep(j, N + 1) {
                chmin(dist[i][j], dist[i][N] + dist[N][x] + dist[x][j]);
            }
            rep(i, N + 1) rep(j, N + 1) {
                chmin(dist[i][j], dist[i][x] + dist[x][N] + dist[N][j]);
            }
        } else {  // t = 3;
            cout << Sum() << '\n';
        }
    }
}