#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    long long arr[n];
    long long diff[n];
    cin >> arr[0];
    diff[0] = arr[0] - 1;
    for (int i = 1; i < n; ++i) {
        cin >> arr[i];
        diff[i] = diff[i-1] + arr[i] - arr[i-1] - 1;
    }
    
    while (q--) {
        long long x;
        cin >> x;
        
        if (x <= diff[0]) cout << x << "\n";
        else if (x > diff[n-1]) cout << arr[n-1] + x - diff[n-1] << "\n";
        else {
            bool done = false;
            int l = 0, r = n, mid;
            
            while (l <= r) {
                mid = (l + r) / 2;
                
                if (x == diff[mid]) {
                    while (diff[mid - 1] == diff[mid]) mid--;
                    cout << arr[mid] - 1 + (x - x) << "\n";
                    done = true;
                    break;
                } else if (x < diff[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            
            if (!done) {
                while (diff[mid] < x) mid++;
                cout << arr[mid] - 1 + (x - diff[mid]) << "\n";
            }
        }
    }
}
#include <bits/stdc++.h>
 
typedef long long ll;
typedef long double ld;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PRECISION cout << fixed << setprecision(20);
 
using namespace std;

template <typename SegNode>
struct SegTree {
    vector<SegNode> tree, arr;
    int n;

    SegTree(int n): n(n) {
        tree.assign(4 * n, 0);
    }

    SegTree(int n, vector<SegNode> arr): n(n) {
        tree.assign(4 * n, 0);
        arr = arr;
        build(0, n - 1, 0);
    }

    SegNode merge(SegNode l, SegNode r) {
        return l + r;
    }

    void build(int ss, int se, int si) {
        if (ss == se) {
            tree[si] = arr[ss];
        } else {
            int mid = ss + se >> 1;
            build(ss, mid, 2 * si + 1);
            build(mid + 1, se, 2 * si + 2);
            tree[si] = merge(tree[2 * si + 1], tree[2 * si + 2]);
        }
    }

    SegNode query(int qs, int qe) {
        return query(qs, qe, 0, n - 1, 0);
    }
 
    SegNode query(int qs, int qe, int ss, int se, int si) {
        if (ss >= qs && se <= qe) {
            return tree[si];
        }

        int mid = ss + se >> 1;
        if (qe <= mid) {
            return query(qs, qe, ss, mid, 2 * si + 1);
        } else if (qs >= mid + 1) {
            return query(qs, qe, mid + 1, se, 2 * si + 2);
        } else {
            return merge(query(qs, qe, ss, mid, 2 * si + 1), query(qs, qe, mid + 1, se, 2 * si + 2));
        }
    }

    void update(int qi, SegNode val) {
        update(qi, val, 0, n - 1, 0);
    }
 
    void update(int qi, SegNode val, int ss, int se, int si) {
        if (ss == se) {
            tree[si] += val;
        } else {
            int mid = ss + se >> 1;
            if (qi <= mid)
                update(qi, val, ss, mid, 2 * si + 1);
            else
                update(qi, val, mid + 1, se, 2 * si + 2);
            tree[si] = merge(tree[2 * si + 1], tree[2 * si + 2]);
        }
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<ll> a(n + 1), b(m + 1);
    vector<array<ll, 3>> queries(q);

    vector<ll> store = {-1, 0};

    for (auto &qu: queries) {
        cin >> qu[0] >> qu[1] >> qu[2];
        store.push_back(qu[2]);
    }

    sort(store.begin(), store.end());
    store.resize(unique(store.begin(), store.end()) - store.begin());

    int len = store.size(); // 0 to len - 1
    map<ll, int> ind;
    for (int i = 0; i < len; i++) ind[store[i]] = i;

    ll suma = 0, sumb = 0, ans = 0;

    SegTree<ll> tsuma(len), tsumb(len), tcnta(len), tcntb(len);

    tcntb.update(ind[0], m);
    tcnta.update(ind[0], n);

    for (auto &qu: queries) {
        ll t = qu[0], x = qu[1], y = qu[2];

        if (t == 1) {
            // change in a
            ll org = sumb - tsumb.query(0, ind[a[x]]) + tcntb.query(0, ind[a[x]]) * a[x];
            ans -= org;
            tsuma.update(ind[a[x]], -a[x]);
            tcnta.update(ind[a[x]], -1);
            suma -= a[x];

            a[x] = y;

            tsuma.update(ind[a[x]], a[x]);
            tcnta.update(ind[a[x]], 1);
            suma += a[x];
            ll act = sumb - tsumb.query(0, ind[a[x]]) + tcntb.query(0, ind[a[x]]) * a[x];
            ans += act;
        } else {
            ll org = suma - tsuma.query(0, ind[b[x]]) + tcnta.query(0, ind[b[x]]) * b[x];
            ans -= org;
            tsumb.update(ind[b[x]], -b[x]);
            tcntb.update(ind[b[x]], -1);
            sumb -= b[x];

            b[x] = y;

            tsumb.update(ind[b[x]], b[x]);
            tcntb.update(ind[b[x]], 1);
            sumb += b[x];
            ll act = suma - tsuma.query(0, ind[b[x]]) + tcnta.query(0, ind[b[x]]) * b[x];
            ans += act;
        }

        cout << ans << "\n";
    }
}

int main() {
    FASTIO;
    PRECISION;

    int t = 1;
    // cin >> t;
    
    for (int i = 0; i < t; i++) {
        solve();
    }
}
