#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int maxm = 2e6 + 5;
//constexpr int maxm = 1e4 + 5;

struct PSA {
    vector<int> psum;

    PSA(const vector<int>& arr) : psum(sz(arr) + 1) {
        partial_sum(begin(arr), end(arr), psum.begin() + 1);
    }

    int query(int l, int r) const {
        return psum[r] - psum[l];
    }
};

struct DS {
    int n, nind[maxm], eind[maxm];
    PSA ew;
    set<int> bad;
    bool blast = false;

    DS(const vector<int>& arr, const vector<pair<int, int>>& edges)
        : n(sz(arr)), ew({}) {
        memset(nind, -1, sizeof(nind));
        memset(eind, -1, sizeof(eind));
        vector<int> ews;
        for (int i = 0; i < n; i++) {
            nind[arr[i]] = i;
            auto& [u, w] = edges[i];
            eind[u] = i;
            ews.push_back(w);
        }
        ew = ews;
    }

    void toggle_edge(int e) {
        e = eind[e];
        if (e == -1) {
            return;
        }
        auto [it, inserted] = bad.insert(e);
        if (!inserted) {
            bad.erase(it);
        }
        blast ^= e == n - 1;
    }

    long query(int u, int v) {
        auto dist = [&](int u, int v) -> long {
            auto it = bad.lower_bound(u);
            if (it != bad.end() && *it < v) {
                return 1e18;
            }
            return ew.query(u, v);
        };
        u = nind[u];
        v = nind[v];
        if (u == -1 || v == -1) {
            return 1e18;
        }
        if (u > v) {
            swap(u, v);
        }
        long ans = dist(u, v);
        if (!blast) {
            ans = min(ans, dist(v, n - 1) + ew.query(n - 1, n) + dist(0, u));
        }
        return ans;
    }
};

void solve() {
    int n, m, kv, q;
    cin >> n >> kv >> m >> q;
    kv--;
    int arrw[n + m + 1];
    for (auto& a : arrw) {
        cin >> a;
    }
    vector<DS> dss;
    auto map_edges = [&](const vector<int>& edges) -> vector<pair<int, int>> {
        vector<pair<int, int>> ans;
        for (auto& a : edges) {
            ans.emplace_back(a, arrw[a]);
        }
        return ans;
    };
    {
        vector<int> nodes, edges;
        for (int i = 0; i < n; i++) {
            nodes.push_back(i);
            edges.push_back(i);
        }
        dss.emplace_back(nodes, map_edges(edges));
    }
    {
        vector<int> nodes {0}, edges {n};
        for (int i = 0; i < m; i++) {
            nodes.push_back(n + i);
            edges.push_back(n + i + 1);
        }
        for (int i = kv; i < n; i++) {
            nodes.push_back(i);
            edges.push_back(i);
        }
        dss.emplace_back(nodes, map_edges(edges));
    }
    {
        vector<int> nodes, edges;
        for (int i = 0; i < kv; i++) {
            nodes.push_back(i);
            edges.push_back(i);
        }
        nodes.push_back(kv);
        edges.push_back(n + m);
        for (int i = m - 1; i >= 0; i--) {
            nodes.push_back(n + i);
            edges.push_back(n + i);
        }
        dss.emplace_back(nodes, map_edges(edges));
    }
    while (q--) {
        char ty;
        cin >> ty;
        if (ty == 'q') {
            auto dist = [&](int u, int v) -> long {
                long ans = 1e18;
                for (auto& ds : dss) {
                    ans = min(ans, ds.query(u, v));
                }
                return ans;
            };
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            long ans = dist(u, v);
            ans = min(ans, dist(u, 0) + dist(0, v));
            if (ans >= long(1e18)) {
                cout << "impossible" << endl;
            } else {
                cout << ans << endl;
            }
        } else if (ty == 'c') {
            int u;
            cin >> u;
            u--;
            for (auto& ds : dss) {
                ds.toggle_edge(u);
            }
        } else if (ty == 'x') {
            int u;
            cin >> u;
            for (auto& ds : dss) {
                ds.toggle_edge(u + n);
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}