import scala.collection.mutable

object Main extends App {
  import scala.io.StdIn._
  val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
  val nodes = Array.tabulate(n){i ⇒
    if (i == 0) DoNothing
    else readLine.trim match {
      case "T=T&X" ⇒ AndX
      case "T=T&Y" ⇒ AndY
      case "T=T|X" ⇒ OrX
      case "T=T|Y" ⇒ OrY
      case "T=T^X" ⇒ XorX
      case "T=T^Y" ⇒ XorY
      case _ ⇒ ???
    }
  }
  val outEdges = Array.tabulate(n){_ ⇒ Nil: List[Int]}
  val edgeCount = Array.tabulate(n){_ ⇒ 0}
  val prevEdge = Array.tabulate(n){_ ⇒ -1}
  for (_ ← 1 until n){
    val Array(u, v) = readLine.trim.split(' ').map(_.toInt)
    outEdges(u) ::= v
    outEdges(v) ::= u
    edgeCount(u) += 1
    edgeCount(v) += 1
  }
  val resultFromRoot = Array.tabulate(n){_ ⇒ Array.tabulate(3){_ ⇒ 0}}
  val depth = Array.tabulate(n){_ ⇒ -1}
  var queue = mutable.Queue[Int](0)
  depth(0) = 0
  while (queue.nonEmpty){
    val top = queue.dequeue()
    for (next ← outEdges(top) if depth(next) == -1){
      depth(next) = depth(top) + 1
      prevEdge(next) = top
      queue.enqueue(next)
      for ((params, i) ← Parameters.nonZeroPatterns){
        resultFromRoot(next)(i) = nodes(next).operation(resultFromRoot(top)(i), params)
      }
    }
  }

  val resultFromLeaf = Array.tabulate(n){_ ⇒ Array.tabulate(6){_ ⇒ 8}}
  var leaves = (1 until n).filter(i ⇒ edgeCount(i) == 1).toList
  for (leaf ← leaves){
    for ((params, i) ← Parameters.allPriorityPatterns){
      resultFromLeaf(leaf)(i) = params.map(_._2).zipWithIndex.map(d ⇒ (1 << (params.length - d._2 - 1)) * resultFromRoot(leaf)(d._1)).sum
    }
  }
  while (leaves.nonEmpty){
    leaves match {
      case h::t ⇒
        for (child ← outEdges(h) if depth(h) < depth(child)){
          if (depth(h) % 2 == 0){
            for (i ← 0 until 6 if resultFromLeaf(h)(i) < resultFromLeaf(child)(i) || resultFromLeaf(h)(i) == 8){
              resultFromLeaf(h)(i) = resultFromLeaf(child)(i)
            }
          }else {
            for (i ← 0 until 6 if resultFromLeaf(h)(i) > resultFromLeaf(child)(i) || resultFromLeaf(h)(i) == 8){
              resultFromLeaf(h)(i) = resultFromLeaf(child)(i)
            }
          }
        }
        if (h != 0) {
          edgeCount(prevEdge(h)) -= 1
          if (prevEdge(h) != 0 && edgeCount(prevEdge(h)) == 1) {
            leaves = prevEdge(h) :: t
          } else if (prevEdge(h) == 0 && edgeCount(0) == 0) {
            leaves = 0 :: t
          } else {
            leaves = t
          }
        }else {
          leaves = Nil
        }
      case Nil ⇒ ???
    }
  }
  for (_ ← 0 until m){
    val Array(x, y) = readLine.trim.split(' ').map(_.toInt)
      if (x == 0 && y == 0) println(0)
      else {
        val (pattern, index) = Parameters.allPriorityWithIndex.filter(p ⇒ isMatchPriority(p._1, x, y)).maxBy(p ⇒ resultFromLeaf(0)(p._2))
        val mapper = pattern.zipWithIndex.map(p ⇒ (p._1, (resultFromLeaf(0)(index) & (1 << (2 - p._2))) != 0))
        val xs = x.toConstLengthBinaryExpression(16)
        val ys = y.toConstLengthBinaryExpression(16)
        println((0 until 16).map(i ⇒ if (mapper.find(_._1 == Parameters(xs(i), ys(i))).exists(_._2)) 1 << (15 - i) else 0).sum)
      }
  }
  implicit class toConstLengthBinaryExpression(val x: Int) extends AnyVal {
    def toConstLengthBinaryExpression(length: Int): Array[Int] = {
      (0 until length).reverse.map(i ⇒ if ((x & (1 << i)) != 0) 1 else 0).toArray
    }
  }

  def isMatchPriority(params: List[Parameters], x: Int, y: Int): Boolean = {
    val a = params.map(p ⇒ p.findFirstIndex(x, y).getOrElse(-1)).toArray
    a.indices.tail.forall(i ⇒ a(i - 1) >= a(i))
  }
  object Parameters {
    val nonZero: List[Parameters] = List(Parameters(0, 1), Parameters(1, 0), Parameters(1, 1))
    val nonZeroPatterns = nonZero.zipWithIndex
    val allPriorityWithIndex = nonZero.permutations.zipWithIndex.toArray
    val allPriorityPatterns = nonZeroPatterns.permutations.toArray.zipWithIndex
  }
  case class Parameters(x: Int, y: Int) {
    def findFirstIndex(x: Int, y: Int): Option[Int] = {
      (0 until 16).reverse.find{d ⇒
        (if (this.x == 0) (x & (1 << d)) == 0
        else (x & (1 << d)) != 0) &&
          (if (this.y == 0) (y & (1 << d)) == 0
        else (y & (1 << d)) != 0)
      }
    }
  }
  sealed trait OperationNode {
    def operation(value: Int, parameters: Parameters): Int
  }
  case object DoNothing extends OperationNode {
    override def operation(value: Int, parameters: Parameters): Int = value
  }
  case object AndX extends OperationNode {
    override def operation(value: Int, parameters: Parameters): Int = value & parameters.x
  }
  case object AndY extends OperationNode {
    override def operation(value: Int, parameters: Parameters): Int = value & parameters.y
  }
  case object OrX extends OperationNode {
    override def operation(value: Int, parameters: Parameters): Int = value | parameters.x
  }
  case object OrY extends OperationNode {
    override def operation(value: Int, parameters: Parameters): Int = value | parameters.y
  }
  case object XorX extends OperationNode {
    override def operation(value: Int, parameters: Parameters): Int = value ^ parameters.x
  }
  case object XorY extends OperationNode {
    override def operation(value: Int, parameters: Parameters): Int = value ^ parameters.y
  }


}


Measured memory_bytes: 496464