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;
}

const operators = [
    "T=T&X",
    "T=T&Y",
    "T=T|X",
    "T=T|Y",
    "T=T^X",
    "T=T^Y"
];

void solve() {
    int N, M;
    scanf("%d %d\n", &N, &M);
    auto O = new int[N];
    foreach (i; 1 .. N) {
        auto s = readln.chomp;
        O[i] = cast(int)(operators.countUntil(s));
    }
    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 0: return t & x;
            case 1: return t & y;
            case 2: return t | x;
            case 3: return t | y;
            case 4: return t ^ x;
            case 5: return t ^ y;
            default: assert(false);
        }
    }

    auto cache = new byte[][][](N, 16, 16);
    foreach (ref a; cache) foreach (ref b; a) b[] = -1;
    int result(int v, int prev, int depth, int t, int x, int y) {
        // bitwise result of game 
        byte res(int v, int prev, int depth, byte t, byte x, byte y) {
            if (cache[v][x][y] >= 0) return cache[v][x][y];
            auto value_func = (delegate(byte a, byte b) {
                    return depth % 2 == 0 ? max(a, b) : min(a, b); // max for A, min for B
                    });
            byte ans = depth % 2 == 0 ? 0 : 100;
            bool last = true;
            foreach (next; T[v]) {
                if (next == prev) continue;
                last = false;
                ans = value_func(ans, res(next, v, depth + 1, cast(byte)op(next, t, x, y), x, y));
            }
            if (last) ans = t;
            return cache[v][x][y] = ans;
        }
        return cast(int)res(v, prev, depth, cast(byte)t, cast(byte) x, cast(byte) y);
    }

    foreach (_; 0 .. M) {
        int X, Y;
        scanf("%d %d\n", &X, &Y);
        bool[Tuple!(int, int)] used;
        int lx, ly;
        for (int i = 15; i >= 0; i--) {
            int x = (X >> i) & 1;
            int y = (Y >> i) & 1;
            auto k = tuple(x, y);
            if (k in used) continue;
            used[k] = true;
            lx = (lx << 1) | x;
            ly = (ly << 1) | y;
        }
        auto bitwise_result = result(0, -1, 0, 0, lx, ly);
        //log([lx, ly], format("%b", bitwise_result));
        int ans;
        for (int i = 15; i >= 0; i--) {
            int x = (X >> i) & 1;
            int y = (Y >> i) & 1;
            for (int j = 0; j < 4; j++) {
                if ( (x == ((lx >> j) & 1)) && (y == ((ly >> j) & 1)) ) {
                    ans |= ((bitwise_result >> j) & 1) << i;
                    break;
                }
            }
        }
        writeln(ans);
    }
}

import core.memory;
alias base_t = long;
const base_t STACK_SIZE = (base_t.sizeof) * (1<<24);
__gshared void* stack;
__gshared base_t org_esp;
__gshared base_t esp;
void main() {
    GC.disable();
    stack = GC.malloc(STACK_SIZE);
    esp = cast(base_t)(stack) + STACK_SIZE - 1;
    asm {
        mov org_esp, RSP;
        mov RSP, esp;
    }

    solve(); 

    asm {
        mov RSP, org_esp;
    }
}

Measured memory_bytes: 261644