F - TREEQUERY

#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x)   (std::isinf(x))
#define IS_NAN(x)   (std::isnan(x))
#define fi   first
#define se   second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }

/* Author: Van Hanh Pham */

/** END OF TEMPLATE. DRINK A CUP OF TIGERSUGAR BEFORE READING MY CODE. **/

#define MAX_TOP   15
const int INF = (int)21e8 + 7LL;

struct Top {
    int value[MAX_TOP];

    Top() {
        REP(i, MAX_TOP) value[i] = -INF;
    }

    int& operator [] (int x) {
        return value[x];
    }
    int operator [] (int x) const {
        return value[x];
    }

    void updateAll(int c) {
        REP(i, MAX_TOP) {
            if (value[i] > -INF) value[i] += c;
            else break;
        }
    }
};

Top merge(const Top &a, const Top &b, int need = MAX_TOP) {
    Top res;
    int x = 0, y = 0;
    REP(i, need) res[i] = a[x] > b[y] ? a[x++] : b[y++];
    return res;
}

class SegmentTree {
private:
    vector<Top> top;
    vector<int> lazy;
    int n;

    void init(int i, int l, int r) {
        if (l > r) return;
        REP(j, min(r - l + 1, MAX_TOP)) top[i][j] = 0;
        if (l == r) return;

        int m = (l + r) >> 1;
        init(2 * i, l, m);
        init(2 * i + 1, m + 1, r);
    }

    void apply(int i, int c) {
        top[i].updateAll(c);
        lazy[i] += c;
    }

    void pushDown(int i) {
        REP(j, 2) apply(2 * i + j, lazy[i]);
        lazy[i] = 0;
    }

    void update(int i, int l, int r, int u, int v, int c) {
        if (l > v || r < u || l > r || v < u) return;
        if (u <= l && r <= v) return apply(i, c);

        pushDown(i);
        int m = (l + r) >> 1;
        update(2 * i, l, m, u, v, c);
        update(2 * i + 1, m + 1, r, u, v, c);

        top[i] = merge(top[2 * i], top[2 * i + 1]);
    }

    Top getPos(int i, int l, int r, int u, int v, int pos) {
        if (l > v || r < u || l > r || v < u) return Top();
        if (u <= l && r <= v) return top[i];

        pushDown(i);
        int m = (l + r) >> 1;
        Top L = getPos(2 * i, l, m, u, v, pos);
        Top R = getPos(2 * i + 1, m + 1, r, u, v, pos);
        return merge(L, R, pos);
    }

public:
    SegmentTree(int n = 0) {
        this->n = n;
        if (n > 0) {
            top.assign(4 * n + 7, Top());
            lazy.assign(4 * n + 7, 0);
            init(1, 1, n);
        }
    }

    void update(int l, int r, int c) {
        update(1, 1, n, l, r, c);
    }

    int getValue(int pos) {
        int i = 1, l = 1, r = n;
        while (true) {
            if (l == r) return top[i][0];
            pushDown(i);
            int m = (l + r) >> 1;
            if (pos > m) {
                i = 2 * i + 1; l = m + 1;
            } else {
                i = 2 * i; r = m;
            }
        }
    }

    Top getPos(int l, int r, int pos) {
        return getPos(1, 1, n, l, r, pos);
    }
};

#define MAX   300300
int numNode, numQuery;
vector<int> children[MAX];
int parity[MAX], treeSize[MAX];
int parityCount[2], sta[2][MAX], fin[2][MAX];
SegmentTree myit[2];

void loadTree(void) {
    int subtask; scanf("%d%d", &subtask, &numNode);
    FOR(i, 2, numNode) {
        int p; scanf("%d", &p);
        children[p].push_back(i);
    }
}

void dfs(int u, int high) {
    REP(i, 2) sta[i][u] = parityCount[i] + 1;
    parity[u] = high;
    parityCount[high]++;

    treeSize[u] = 1;
    FORE(it, children[u]) {
        dfs(*it, high ^ 1);
        treeSize[u] += treeSize[*it];
    }

    REP(i, 2) fin[i][u] = parityCount[i];
}

void update(int node, int delta) {
    REP(i, 2) myit[i].update(sta[i][node], fin[i][node], i == parity[node] ? delta : -delta);
}

int getValue(int node) {
    return myit[parity[node]].getValue(sta[parity[node]][node]);
}

int getPos(int node, int pos) {
    if (treeSize[node] < pos) return 0;

    Top top[2];
    REP(i, 2) top[i] = myit[i].getPos(sta[i][node], fin[i][node], pos);
    return merge(top[0], top[1], pos)[pos - 1];
}

void process(void) {
    dfs(1, 0);
    REP(i, 2) myit[i] = SegmentTree(parityCount[i]);

    char input[6];
    int node;
    scanf("%d", &numQuery);
    REP(love, numQuery) {
        scanf("%s", input);
        scanf("%d", &node);

        switch (input[0]) {
        case 'a':
            int delta; scanf("%d", &delta);
            update(node, delta);
            break;

        case 'g':
            printf("%d ", getValue(node));
            break;

        case 'p':
            int pos; scanf("%d", &pos);
            printf("%d ", getPos(node, pos));
            break;

        default:
            cout << "Strange query" << endl;
            assert(false);
        }
    }

    printf("\n");
}

int main(void) {
#ifdef ONLINE_JUDGE
    freopen("query.inp", "r", stdin);
    freopen("query.out", "w", stdout);
#endif // ONLINE_JUDGE

    loadTree();
    process();
    return 0;
}

/*** BUBBLE TEA IS GREAT. MY CODE IS AMAZING :D ***/