import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void log(A...)(A arg) {
    stderr.writeln(arg);
}
int size(T)(in T s) {
    return cast(int)s.length;
}

void main() {
    int N, M;
    scanf("%d %d\n", &N, &M);
    auto O = new string[N];
    foreach (i; 1 .. N) {
        O[i] = readln.chomp;
    }
    auto T = new int[][N];
    foreach (i; 0 .. N - 1) {
        int u, v; scanf("%d %d\n", &u, &v);
        T[u] ~= v;
        T[v] ~= u;
    }

    int op(int v, int t, int x, int y) {
        switch (O[v]) {
            case "T=T&X": return t & x;
            case "T=T&Y": return t & y;
            case "T=T|X": return t | x;
            case "T=T|Y": return t | y;
            case "T=T^X": return t ^ x;
            case "T=T^Y": return t ^ y;
            default: assert(false);
        }
    }

    int[Tuple!(int, int, int, int)] path;
    // bitwise result of game 
    int result(int v, int prev, int depth, int t, int x, int y) {
        static int[Tuple!(int, int, int, int)] cache;
        assert(t == 0 || t == 1);
        auto key = tuple(v, t, x, y);
        if (key in cache) return cache[key];
        auto value_func = (delegate(int a, int b) {
            return depth % 2 == 0 ? max(a, b) : min(a, b); // max for A, min for B
        });
        int ans = depth % 2 == 0 ? 0 : 1;
        int opt_next = -1;
        foreach (next; T[v]) {
            if (next == prev) continue;
            int z = result(next, v, depth + 1, op(next, t, x, y) & 1, x, y);
            if (z == value_func(ans, z)) {
                // z is more or equaly valuable than current ans
                ans = z;
                opt_next = next;
            }
        }
        path[key] = opt_next;
        if (opt_next < 0) return cache[key] = t; // if there's no turn, then t is the answer
        else return cache[key] = ans;
    }
    foreach (int j; 0 .. 2) foreach (int k; 0 .. 2) result(0, -1, 0, 0, j, k);

    int final_result[Tuple!(int, int, int, int)];
    void calc_final_result(int v, int prev, int depth, int pathgen_t, int t, int pathgen_x, int pathgen_y, int x, int y) {
        assert(t == 0 || t == 1);
        auto key = tuple(v, pathgen_t, pathgen_x, pathgen_y);
        auto value_func = (delegate(int a, int b) {
            return depth % 2 == 0 ? max(a, b) : min(a, b); // max for A, min for B
        });
        int ans = depth % 2 == 0 ? 0 : 1;
        int next = path[key];
        assert(next != prev);
        if (next >= 0) {
            calc_final_result(next, v, depth + 1, op(next, pathgen_t, pathgen_x, pathgen_y) & 1, op(next, t, x, y) & 1, pathgen_x, pathgen_y, x, y);
        } else {
            final_result[tuple(pathgen_x, pathgen_y, x, y)] = t;
        }
    }
    foreach (int a; 0 .. 2) foreach (int b; 0 .. 2) foreach (int j; 0 .. 2) foreach (int k; 0 .. 2) calc_final_result(0, -1, 0, 0, 0, a, b, j, k);

    //log(final_result);

    foreach (_; 0 .. M) {
        int X, Y;
        scanf("%d %d\n", &X, &Y);
        int ans = 0;
        foreach (int a; 0 .. 2) foreach (int b; 0 .. 2) {
            int cand = 0;
            for (int j = 15; j >= 0; j--) {
                cand |= (final_result[tuple(a, b, (X >> j) & 1, (Y >> j) & 1)] << j);
            }
            ans = max(ans, cand);
        }
        writeln(ans);
    }
}