description: <image>
  
  As mentioned previously William really likes playing video games. In one of his favorite games, the player character is in a universe where every planet is designated by a binary number from 0 to 2^n - 1. On each planet, there are gates that allow the player to move from planet i to planet j if the binary representations of i and j differ in exactly one bit.
  
  William wants to test you and see how you can handle processing the following queries in this game universe:
  
    * Destroy planets with numbers from l to r inclusively. These planets cannot be moved to anymore.
    * Figure out if it is possible to reach planet b from planet a using some number of planetary gates. It is guaranteed that the planets a and b are not destroyed. 
  
  Input
  
  The first line contains two integers n, m (1 ≤ n ≤ 50, 1 ≤ m ≤ 5 ⋅ 10^4), which are the number of bits in binary representation of each planets' designation and the number of queries, respectively.
  
  Each of the next m lines contains a query of two types:
  
  block l r — query for destruction of planets with numbers from l to r inclusively (0 ≤ l ≤ r < 2^n). It's guaranteed that no planet will be destroyed twice.
  
  ask a b — query for reachability between planets a and b (0 ≤ a, b < 2^n). It's guaranteed that planets a and b hasn't been destroyed yet.
  
  Output
  
  For each query of type ask you must output "1" in a new line, if it is possible to reach planet b from planet a and "0" otherwise (without quotation marks).
  
  Examples
  
  Input
  
  
  3 3
  ask 0 7
  block 3 6
  ask 0 7
  
  
  Output
  
  
  1
  0
  
  
  Input
  
  
  6 10
  block 12 26
  ask 44 63
  block 32 46
  ask 1 54
  block 27 30
  ask 10 31
  ask 11 31
  ask 49 31
  block 31 31
  ask 2 51
  
  
  Output
  
  
  1
  1
  0
  0
  1
  0
  
  Note
  
  The first example test can be visualized in the following way:
  
  <image>
  
  Response to a query ask 0 7 is positive.
  
  Next after query block 3 6 the graph will look the following way (destroyed vertices are highlighted):
  
  <image>
  
  Response to a query ask 0 7 is negative, since any path from vertex 0 to vertex 7 must go through one of the destroyed vertices.
solution: import java.io.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.util.Arrays;
  import java.util.ArrayList;
  import java.io.OutputStream;
  import java.io.PrintStream;
  import java.io.IOException;
  import java.lang.reflect.Field;
  import java.nio.charset.StandardCharsets;
  import java.io.UncheckedIOException;
  import java.util.List;
  import java.io.Closeable;
  import java.util.Comparator;
  import java.util.Collections;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   */
  public class Main {
      public static void main(String[] args) throws Exception {
          new TaskAdapter().run();
      }
  
      static class TaskAdapter implements Runnable {
          @Override
          public void run() {
              InputStream inputStream = System.in;
              OutputStream outputStream = System.out;
              FastInput in = new FastInput(inputStream);
              FastOutput out = new FastOutput(outputStream);
              GGatesToAnotherWorld solver = new GGatesToAnotherWorld();
              solver.solve(1, in, out);
              out.close();
          }
      }
  
      static class GGatesToAnotherWorld {
          Debug debug = new Debug(false);
          DSU dsu;
          List<Node> nodeList;
  
          public void solve(int testNumber, FastInput in, FastOutput out) {
              int n = in.ri();
              int m = in.ri();
              List<Query> qs = new ArrayList<>(m);
              List<Query> updates = new ArrayList<>(m);
              for (int i = 0; i < m; i++) {
                  int t = in.rs().equals("block") ? 0 : 1;
                  Query q = new Query(t, in.rl(), in.rl());
                  qs.add(q);
                  if (q.type == 0) {
                      updates.add(q);
                  }
              }
              debug.debug("updates", updates);
              List<Query> revQs = new ArrayList<>(qs);
              Collections.reverse(revQs);
              debug.debug("revQs", revQs);
              nodeList = new ArrayList<>(m * 2);
              updates.sort(Comparator.comparingLong(x -> x.l));
              long last = 0;
              for (Query q : updates) {
                  long l = last;
                  long r = q.l - 1;
                  addNode(l, r, false);
                  addNode(q.l, q.r, true);
                  last = q.r + 1;
              }
              addNode(last, (1L << n) - 1, false);
              debug.elapse("createNode");
              Node[] nodes = nodeList.toArray(new Node[0]);
              debug.debug("nodes", nodes);
              for (int i = 0; i < nodes.length; i++) {
                  nodes[i].id = i;
              }
              assert SortUtils.notStrictAscending(nodes, 0, nodes.length - 1, Comparator.comparingLong(x -> x.l));
              dac(nodes, 0, nodes.length - 1, 0, (1L << n) - 1, n - 1);
  
              dsu = new DSU(nodes.length);
              dsu.init();
  
              for (Node root : nodes) {
                  recalc(root);
              }
  
              debug.elapse("build");
  
  //        search(nodes, nodes[0], nodes[12]);
  //        for(Node cur = nodes[12]; cur != null; cur = cur.prev){
  //            debug.debug("cur", cur);
  //        }
              for (Query q : revQs) {
                  Node a = search(nodes, q.l);
                  Node b = search(nodes, q.r);
                  if (q.type == 0) {
                      assert a.del;
                      assert b.del;
                      a.del = false;
                      b.del = false;
                      recalc(a);
                      recalc(b);
                  } else {
                      assert !a.del;
                      assert !b.del;
                      q.ans = dsu.find(a.id) == dsu.find(b.id);
                  }
              }
  
              debug.elapse("answer");
              for (Query q : qs) {
                  if (q.type == 1) {
                      out.println(q.ans ? 1 : 0);
                  }
              }
          }
  
          public boolean intersect(long l, long r, long L, long R) {
              return l <= R && r >= L;
          }
  
          public boolean checkInRange(Node[] nodes, int l, int r, long L, long R) {
              for (int i = l; i <= r; i++) {
                  if (nodes[i].l < L || nodes[i].r > R) {
                      return false;
                  }
              }
              return true;
          }
  
          public void dac(Node[] nodes, int l, int r, long L, long R, int D) {
              assert checkInRange(nodes, l, r, L, R);
              if (l >= r) {
                  return;
              }
              if (D < 0) {
                  assert l == r;
              }
              long M = (L + R) / 2;
              int ml = l - 1;
              while (ml + 1 <= r && nodes[ml + 1].r <= M) {
                  ml++;
              }
              int mr = r + 1;
              while (mr - 1 >= l && nodes[mr - 1].l > M) {
                  mr--;
              }
  
              dac(nodes, l, ml, L, M, D - 1);
              dac(nodes, mr, r, M + 1, R, D - 1);
  
              if (ml + 1 < mr) {
                  for (int j = ml + 1; j < mr; j++) {
                      for (int i = l; i <= ml; i++) {
                          addEdge(nodes[i], nodes[j]);
                      }
                      for (int i = mr; i <= r; i++) {
                          addEdge(nodes[i], nodes[j]);
                      }
                  }
              } else {
                  int lIter = l;
                  int rIter = mr;
                  long mask = (1L << D) - 1;
                  while (lIter <= ml && rIter <= r) {
                      int comp = Long.compare(nodes[lIter].r & mask, nodes[rIter].r & mask);
                      if (intersect(nodes[lIter].l & mask, nodes[lIter].r & mask,
                              nodes[rIter].l & mask, nodes[rIter].r & mask)) {
                          addEdge(nodes[lIter], nodes[rIter]);
                      }
                      if (comp <= 0) {
                          lIter++;
                      }
                      if (comp >= 0) {
                          rIter++;
                      }
                  }
              }
          }
  
          public void recalc(Node root) {
              if (root.del) {
                  return;
              }
              for (Node node : root.adj) {
                  if (node.del) {
                      continue;
                  }
                  dsu.merge(root.id, node.id);
              }
          }
  
          public boolean check(Node a, Node b) {
              for (int i = 0; i < 50; i++) {
                  for (long j = a.l; j <= a.r; j++) {
                      long to = j ^ (1L << i);
                      if (b.l <= to && b.r >= to) {
                          return true;
                      }
                  }
              }
              return false;
          }
  
          public void addEdge(Node a, Node b) {
              assert check(a, b);
              a.adj.add(b);
              b.adj.add(a);
          }
  
          public Node search(Node[] nodes, long x) {
              int l = 0;
              int r = nodes.length - 1;
              while (l < r) {
                  int m = (l + r + 1) >> 1;
                  if (nodes[m].l <= x) {
                      l = m;
                  } else {
                      r = m - 1;
                  }
              }
              return nodes[l];
          }
  
          void addNode(long l, long r, boolean del) {
              if (r < l) {
                  return;
              }
              if (l == r) {
                  addNode0(l, r, del);
                  return;
              }
              int index = Bits.theFirstDifferentIndex(l, r);
              long prefix = (l >> (index + 1)) << (index + 1);
              long mid = prefix | (1L << index);
              addNode0(l, mid - 1, del);
              addNode0(mid, r, del);
          }
  
          void addNode0(long l, long r, boolean del) {
              if (r < l) {
                  return;
              }
              nodeList.add(new Node(l, r, del));
          }
  
      }
  
      static class Bits {
          private Bits() {
          }
  
          public static int theFirstDifferentIndex(long x, long y) {
              return Log2.floorLog(x ^ y);
          }
  
      }
  
      static class FastOutput implements AutoCloseable, Closeable, Appendable {
          private static final int THRESHOLD = 32 << 10;
          private OutputStream writer;
          private StringBuilder cache = new StringBuilder(THRESHOLD * 2);
          private static Field stringBuilderValueField;
          private char[] charBuf = new char[THRESHOLD * 2];
          private byte[] byteBuf = new byte[THRESHOLD * 2];
  
          static {
              try {
                  stringBuilderValueField = StringBuilder.class.getSuperclass().getDeclaredField("value");
                  stringBuilderValueField.setAccessible(true);
              } catch (Exception e) {
                  stringBuilderValueField = null;
              }
              stringBuilderValueField = null;
          }
  
          public FastOutput append(CharSequence csq) {
              cache.append(csq);
              return this;
          }
  
          public FastOutput append(CharSequence csq, int start, int end) {
              cache.append(csq, start, end);
              return this;
          }
  
          private void afterWrite() {
              if (cache.length() < THRESHOLD) {
                  return;
              }
              flush();
          }
  
          public FastOutput(OutputStream writer) {
              this.writer = writer;
          }
  
          public FastOutput append(char c) {
              cache.append(c);
              afterWrite();
              return this;
          }
  
          public FastOutput append(int c) {
              cache.append(c);
              afterWrite();
              return this;
          }
  
          public FastOutput println(int c) {
              return append(c).println();
          }
  
          public FastOutput println() {
              return append('\n');
          }
  
          public FastOutput flush() {
              try {
                  if (stringBuilderValueField != null) {
                      try {
                          byte[] value = (byte[]) stringBuilderValueField.get(cache);
                          writer.write(value, 0, cache.length());
                      } catch (Exception e) {
                          stringBuilderValueField = null;
                      }
                  }
                  if (stringBuilderValueField == null) {
                      int n = cache.length();
                      if (n > byteBuf.length) {
                          //slow
                          writer.write(cache.toString().getBytes(StandardCharsets.UTF_8));
  //                writer.append(cache);
                      } else {
                          cache.getChars(0, n, charBuf, 0);
                          for (int i = 0; i < n; i++) {
                              byteBuf[i] = (byte) charBuf[i];
                          }
                          writer.write(byteBuf, 0, n);
                      }
                  }
                  writer.flush();
                  cache.setLength(0);
              } catch (IOException e) {
                  throw new UncheckedIOException(e);
              }
              return this;
          }
  
          public void close() {
              flush();
              try {
                  writer.close();
              } catch (IOException e) {
                  throw new UncheckedIOException(e);
              }
          }
  
          public String toString() {
              return cache.toString();
          }
  
      }
  
      static class Debug {
          private boolean offline;
          private PrintStream out = System.err;
          private long time = System.currentTimeMillis();
          static int[] empty = new int[0];
  
          public Debug(boolean enable) {
              offline = enable && System.getSecurityManager() == null;
          }
  
          public Debug elapse(String name) {
              if (offline) {
                  debug(name, System.currentTimeMillis() - time);
                  time = System.currentTimeMillis();
              }
              return this;
          }
  
          public Debug debug(String name, long x) {
              if (offline) {
                  debug(name, "" + x);
              }
              return this;
          }
  
          public Debug debug(String name, String x) {
              if (offline) {
                  out.printf("%s=%s", name, x);
                  out.println();
              }
              return this;
          }
  
          public Debug debug(String name, Object x) {
              return debug(name, x, empty);
          }
  
          public Debug debug(String name, Object x, int... indexes) {
              if (offline) {
                  if (x == null || !x.getClass().isArray()) {
                      out.append(name);
                      for (int i : indexes) {
                          out.printf("[%d]", i);
                      }
                      out.append("=").append("" + x);
                      out.println();
                  } else {
                      indexes = Arrays.copyOf(indexes, indexes.length + 1);
                      if (x instanceof byte[]) {
                          byte[] arr = (byte[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof short[]) {
                          short[] arr = (short[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof boolean[]) {
                          boolean[] arr = (boolean[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof char[]) {
                          char[] arr = (char[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof int[]) {
                          int[] arr = (int[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof float[]) {
                          float[] arr = (float[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof double[]) {
                          double[] arr = (double[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof long[]) {
                          long[] arr = (long[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else {
                          Object[] arr = (Object[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      }
                  }
              }
              return this;
          }
  
      }
  
      static class DSU {
          protected int[] p;
          public int[] size;
          protected int n;
  
          public DSU(int n) {
              p = new int[n];
              size = new int[n];
          }
  
          public void init() {
              init(p.length);
          }
  
          public void init(int n) {
              this.n = n;
              for (int i = 0; i < n; i++) {
                  p[i] = i;
                  size[i] = 1;
              }
          }
  
          public final int find(int a) {
              if (p[a] == p[p[a]]) {
                  return p[a];
              }
              find(p[a]);
              preAccess(a);
              return p[a] = p[p[a]];
          }
  
          protected void preAccess(int a) {
  
          }
  
          protected void preMerge(int a, int b) {
              size[a] += size[b];
          }
  
          public final void merge(int a, int b) {
              a = find(a);
              b = find(b);
              if (a == b) {
                  return;
              }
  
              if (size[a] < size[b]) {
                  int tmp = a;
                  a = b;
                  b = tmp;
              }
              preMerge(a, b);
              p[b] = a;
          }
  
          public String toString() {
              return Arrays.toString(Arrays.copyOf(p, n));
          }
  
      }
  
      static class Log2 {
          public static int floorLog(long x) {
              if (x <= 0) {
                  throw new IllegalArgumentException();
              }
              return 63 - Long.numberOfLeadingZeros(x);
          }
  
      }
  
      static class Query {
          int type;
          long l;
          long r;
          boolean ans;
  
          public Query(int type, long l, long r) {
              this.type = type;
              this.l = l;
              this.r = r;
          }
  
          public String toString() {
              return "Query{" +
                      "type=" + type +
                      ", l=" + l +
                      ", r=" + r +
                      '}';
          }
  
      }
  
      static class SortUtils {
          private SortUtils() {
          }
  
          public static <T> boolean notStrictAscending(T[] data, int l, int r, Comparator<T> comp) {
              for (int i = l + 1; i <= r; i++) {
                  if (comp.compare(data[i], data[i - 1]) < 0) {
                      return false;
                  }
              }
              return true;
          }
  
      }
  
      static class Node {
          long l;
          long r;
          boolean del;
          int id;
          List<Node> adj = new ArrayList<>();
  
          public Node(long l, long r, boolean del) {
              this.l = l;
              this.r = r;
              this.del = del;
          }
  
          public String toString() {
              return "Node{" +
                      "l=" + l +
                      ", r=" + r +
                      ", del=" + del +
                      ", id=" + id +
                      '}';
          }
  
      }
  
      static class FastInput {
          private final InputStream is;
          private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
          private byte[] buf = new byte[1 << 13];
          private int bufLen;
          private int bufOffset;
          private int next;
  
          public FastInput(InputStream is) {
              this.is = is;
          }
  
          private int read() {
              while (bufLen == bufOffset) {
                  bufOffset = 0;
                  try {
                      bufLen = is.read(buf);
                  } catch (IOException e) {
                      bufLen = -1;
                  }
                  if (bufLen == -1) {
                      return -1;
                  }
              }
              return buf[bufOffset++];
          }
  
          public void skipBlank() {
              while (next >= 0 && next <= 32) {
                  next = read();
              }
          }
  
          public int ri() {
              return readInt();
          }
  
          public int readInt() {
              boolean rev = false;
  
              skipBlank();
              if (next == '+' || next == '-') {
                  rev = next == '-';
                  next = read();
              }
  
              int val = 0;
              while (next >= '0' && next <= '9') {
                  val = val * 10 - next + '0';
                  next = read();
              }
  
              return rev ? val : -val;
          }
  
          public long rl() {
              return readLong();
          }
  
          public long readLong() {
              boolean rev = false;
  
              skipBlank();
              if (next == '+' || next == '-') {
                  rev = next == '-';
                  next = read();
              }
  
              long val = 0;
              while (next >= '0' && next <= '9') {
                  val = val * 10 - next + '0';
                  next = read();
              }
  
              return rev ? val : -val;
          }
  
          public String rs() {
              return readString();
          }
  
          public String readString(StringBuilder builder) {
              skipBlank();
  
              while (next > 32) {
                  builder.append((char) next);
                  next = read();
              }
  
              return builder.toString();
          }
  
          public String readString() {
              defaultStringBuf.setLength(0);
              return readString(defaultStringBuf);
          }
  
      }
  }
  
  