#include <bits/stdc++.h>
#pragma warning(disable : 4996)
namespace apa {
using namespace std;
template <typename T>
class ComparisonOperators {
  friend bool operator==(T const& lhs, T const& rhs) {
    return lhs.compare(rhs) == 0;
  }
  friend bool operator!=(T const& lhs, T const& rhs) {
    return lhs.compare(rhs) != 0;
  }
  friend bool operator<(T const& lhs, T const& rhs) {
    return lhs.compare(rhs) < 0;
  }
  friend bool operator>(T const& lhs, T const& rhs) {
    return rhs.compare(lhs) < 0;
  }
  friend bool operator<=(T const& lhs, T const& rhs) {
    bool result = lhs.compare(rhs) <= 0;
    return result;
  }
  friend bool operator>=(T const& lhs, T const& rhs) {
    return rhs.compare(lhs) <= 0;
  }
};
class lint : ComparisonOperators<lint> {
 public:
  explicit lint(std::string number);
  lint();
  lint(long long number);
  lint(int number);
  lint(double number);
  lint(vector<int> nums, bool is_neg);
  lint(const lint& obj);
  int get_length() const;
  bool is_negative_number() const;
  lint& operator+=(const lint& b);
  lint& operator-=(const lint& b);
  lint& operator*=(const lint& number2);
  lint& operator/=(const lint& b);
  explicit operator bool() const;
  explicit operator int();
  lint operator+() const;
  lint operator-() const;
  int operator[](size_t index) const;
  lint& operator=(const lint& other);
  lint& operator++();
  lint operator++(int);
  lint& operator--();
  lint operator--(int);
  bool cmp(lint const& rhs) const;
  int compare(lint const& rhs) const;
  bool is_zero() const;
  std::string to_string();

 private:
  bool is_negative;
  vector<int> numbers;
  lint abs(lint number) const;
  vector<int> reverse_numbers(vector<int> const& numbers) const;
  void make_equal_length(const lint& b, vector<int>& number1,
                         vector<int>& number2) const;
  void string_to_vector(std::string const& number);
  void integer_to_vector(long long a);
};
lint abs(lint number);
lint pow(lint a, int n);
std::ostream& operator<<(std::ostream& os, const lint& obj);
std::istream& operator>>(std::istream& is, lint& obj);
lint operator+(const lint& lhs, const lint& rhs);
lint operator-(const lint& lhs, const lint& rhs);
lint operator*(const lint& lhs, const lint& rhs);
lint operator/(const lint& lhs, const lint& rhs);
}  // namespace apa
namespace apa {
lint::lint(std::string number) { string_to_vector(number); }
lint::lint() { integer_to_vector(0); }
lint::lint(long long number) { integer_to_vector(number); }
lint::lint(int number) { integer_to_vector(static_cast<long long>(number)); }
lint::lint(double number) {
  std::string str = std::to_string(std::trunc(number));
  std::string result = str.substr(0, str.size() - 7);
  string_to_vector(result);
}
lint::lint(vector<int> nums, bool is_neg) {
  numbers = nums;
  is_negative = is_neg;
}
lint::lint(const lint& obj) {
  is_negative = obj.is_negative_number();
  for (int t : obj.numbers) {
    numbers.push_back(t);
  }
}
int lint::get_length() const { return numbers.size(); }
bool lint::is_negative_number() const { return is_negative; }
lint& lint::operator+=(const lint& b) {
  if (!is_negative_number() && b.is_negative_number()) {
    lint temp(b);
    temp = abs(temp);
    return operator-=(temp);
  }
  if (is_negative_number() && !b.is_negative_number()) {
    lint temp_this = lint(*this);
    temp_this.is_negative = false;
    lint temp = lint(b);
    temp -= temp_this;
    *this = temp;
    return *this;
  }
  vector<int> number1;
  vector<int> number2;
  make_equal_length(b, number1, number2);
  vector<int> result;
  int rest = 0;
  for (int i = number1.size() - 1; i >= 0; --i) {
    int sum = number1[i] + number2[i] + rest;
    if (sum > 9) {
      rest = 1;
      sum -= 10;
    } else {
      rest = 0;
    }
    result.push_back(sum);
  }
  if (rest > 0) {
    result.push_back(rest);
  }
  vector<int> reverse_result = reverse_numbers(result);
  (*this).numbers = reverse_result;
  return *this;
}
lint& lint::operator-=(const lint& b) {
  if (!is_negative_number() && b.is_negative_number()) {
    return (*this).operator+=(abs(b));
  }
  if (is_negative_number() && !b.is_negative_number()) {
    lint temp(b);
    temp.is_negative = true;
    return (*this).operator+=(temp);
  }
  vector<int> number1;
  vector<int> number2;
  make_equal_length(b, number1, number2);
  int is_number1_more_than_number2 = 0;
  for (unsigned int i = 0; i < number1.size(); ++i) {
    if (number1[i] > number2[i]) {
      is_number1_more_than_number2 = 1;
      break;
    } else if (number1[i] < number2[i]) {
      is_number1_more_than_number2 = 2;
      break;
    }
  }
  if (is_number1_more_than_number2 == 0) {
    vector<int> t;
    t.push_back(0);
    numbers = t;
    return *this;
  }
  vector<int> result;
  if (is_number1_more_than_number2 == 1) {
    for (int i = number1.size() - 1; i >= 0; --i) {
      if (number1[i] < number2[i]) {
        number1[i] += 10;
        number1[i - 1] -= 1;
      }
      int r = number1[i] - number2[i];
      result.push_back(r);
    }
  } else if (is_number1_more_than_number2 == 2) {
    for (int i = number2.size() - 1; i >= 0; --i) {
      if (number2[i] < number1[i]) {
        number2[i] += 10;
        number2[i - 1] -= 1;
      }
      int r = number2[i] - number1[i];
      result.push_back(r);
    }
  }
  bool can_copy = false;
  vector<int> result_without_zero;
  for (int i = result.size() - 1; i >= 0; --i) {
    if (result[i] != 0) {
      can_copy = true;
    }
    if (can_copy) {
      result_without_zero.push_back(result[i]);
    }
  }
  (*this).numbers = result_without_zero;
  if (!is_negative_number() && !b.is_negative_number()) {
    if (is_number1_more_than_number2 == 2) {
      is_negative = true;
    }
  }
  if (is_negative_number() && b.is_negative_number()) {
    if (is_number1_more_than_number2 == 2) {
      is_negative = false;
    }
  }
  return *this;
}
lint& lint::operator*=(const lint& number2) {
  vector<int> a = reverse_numbers(numbers);
  vector<int> b = reverse_numbers(number2.numbers);
  vector<int> c(a.size() + b.size(), 0);
  for (size_t i = 0; i < a.size(); ++i) {
    int carry = 0;
    for (unsigned int j = 0; j < b.size() || carry; ++j) {
      long long cur = c[i + j] + a[i] * 1ll * (j < b.size() ? b[j] : 0) + carry;
      c[i + j] = int(cur % 10);
      carry = int(cur / 10);
    }
  }
  while (c.size() > 1 && c.back() == 0) {
    c.pop_back();
  }
  vector<int> result = reverse_numbers(c);
  numbers = result;
  if (is_negative_number() && !number2.is_negative_number()) {
    is_negative = true;
  } else if (!is_negative_number() && number2.is_negative_number()) {
    is_negative = true;
  } else {
    is_negative = false;
  }
  return *this;
}
lint& lint::operator/=(const lint& number2) {
  if (number2.is_zero()) {
    int d = 4 - 4;
    int a = 4 / d;
    numbers.push_back(a);
  }
  if (is_zero()) {
    vector<int> temp;
    temp.push_back(0);
    numbers = temp;
    is_negative = false;
    return *this;
  }
  bool second_number_more_then_first_number = abs(*this).cmp(abs(number2));
  if (second_number_more_then_first_number) {
    vector<int> temp;
    temp.push_back(0);
    numbers = temp;
    is_negative = false;
    return *this;
  }
  vector<int> res;
  for (int i = (*this).get_length() - 1; i >= 0; --i) {
    res.push_back(0);
  }
  lint current_value(0);
  for (int i = 0; i < (*this).get_length(); ++i) {
    current_value = current_value * 10;
    current_value.numbers[current_value.get_length() - 1] = (*this).numbers[i];
    int x = 0;
    int left_index = 0;
    int right_index = 10;
    while (left_index <= right_index) {
      int middle = (left_index + right_index) >> 1;
      lint cur = abs(number2) * middle;
      if (abs(cur) <= abs(current_value)) {
        x = middle;
        left_index = middle + 1;
      } else {
        right_index = middle - 1;
      }
    }
    res[i] = x;
    current_value = current_value - abs(number2) * x;
  }
  res = reverse_numbers(res);
  while (res.size() > 1 && res.back() == 0) {
    res.pop_back();
  }
  res = reverse_numbers(res);
  numbers = res;
  if (is_negative_number() && !number2.is_negative_number()) {
    is_negative = true;
  } else if (!is_negative_number() && number2.is_negative_number()) {
    is_negative = true;
  } else {
    is_negative = false;
  }
  return *this;
}
lint::operator bool() const { return !is_zero(); }
lint::operator int() { return std::stoi((*this).to_string()); }
lint lint::operator+() const {
  lint temp(*this);
  return temp;
}
lint lint::operator-() const {
  lint temp(*this);
  if (is_negative_number()) {
    temp.is_negative = false;
  } else {
    temp.is_negative = true;
  }
  return temp;
}
int lint::operator[](size_t index) const { return numbers[index]; }
lint& lint::operator=(const lint& other) {
  if (this != &other) {
    numbers = other.numbers;
    is_negative = other.is_negative_number();
  }
  return *this;
}
lint& lint::operator++() {
  lint one(1);
  (*this) += one;
  return *this;
}
lint lint::operator++(int) {
  lint tmp(*this);
  operator++();
  return tmp;
}
lint& lint::operator--() {
  lint one(1);
  (*this) -= one;
  return *this;
}
lint lint::operator--(int) {
  lint tmp(*this);
  operator--();
  return tmp;
}
bool lint::cmp(lint const& rhs) const {
  if (is_negative_number() && !rhs.is_negative_number()) {
    return true;
  }
  if (!is_negative_number() && rhs.is_negative_number()) {
    return false;
  }
  if (get_length() < rhs.get_length()) {
    return true;
  }
  if (get_length() > rhs.get_length()) {
    return false;
  }
  for (int i = 0; i < get_length(); ++i) {
    if (numbers[i] < rhs[i]) {
      if (is_negative_number()) {
        return false;
      }
      return true;
    } else if (numbers[i] > rhs[i]) {
      if (is_negative_number()) {
        return true;
      }
      return false;
    }
  }
  return false;
}
int lint::compare(lint const& rhs) const {
  if ((*this).cmp(rhs)) {
    return -1;
  } else if (rhs.cmp(*this)) {
    return 1;
  } else {
    return 0;
  }
}
lint lint::abs(lint number) const {
  number.is_negative = false;
  return number;
}
bool lint::is_zero() const {
  if (numbers.size() == 1 && numbers[0] == 0) {
    return true;
  }
  return false;
}
std::string int_to_string(int i) {
  std::stringstream ss;
  std::string s;
  ss << i;
  s = ss.str();
  return s;
}
std::string lint::to_string() {
  std::string result = "";
  if (is_negative_number() && !is_zero()) {
    result += "-";
  }
  for (int i = 0; i < get_length(); ++i) {
    int a = (*this)[i];
    result += int_to_string(a);
  }
  return result;
}
vector<int> lint::reverse_numbers(vector<int> const& numbers) const {
  vector<int> reverse_result;
  for (int i = numbers.size() - 1; i >= 0; --i) {
    reverse_result.push_back(numbers[i]);
  }
  return reverse_result;
}
void lint::make_equal_length(lint const& b, vector<int>& number1,
                             vector<int>& number2) const {
  int diff_length = get_length() - b.get_length();
  if (diff_length > 0) {
    number1 = (*this).numbers;
    for (int i = 0; i < diff_length; ++i) {
      number2.push_back(0);
    }
    for (int i = 0; i < b.get_length(); ++i) {
      number2.push_back(b[i]);
    }
  } else if (diff_length < 0) {
    for (int i = 0; i < b.get_length(); ++i) {
      number2.push_back(b[i]);
    }
    for (int i = 0; i < (diff_length * (-1)); ++i) {
      number1.push_back(0);
    }
    for (int i = 0; i < get_length(); ++i) {
      number1.push_back((*this)[i]);
    }
  } else {
    for (int i = 0; i < b.get_length(); ++i) {
      number1.push_back((*this)[i]);
      number2.push_back(b[i]);
    }
  }
}
void lint::string_to_vector(std::string const& number) {
  unsigned int from = 0;
  if (number[0] == '-') {
    is_negative = true;
    from = 1;
  } else {
    is_negative = false;
  }
  for (unsigned int i = from; i < number.length(); ++i) {
    int ia = number[i] - '0';
    numbers.push_back(ia);
  }
}
void lint::integer_to_vector(long long a) {
  if (a < 0) {
    is_negative = true;
    a = (-1) * a;
  } else {
    is_negative = false;
  }
  if (a == 0) {
    numbers.push_back(0);
  }
  vector<int> temp;
  while (a) {
    int x = a % 10;
    a /= 10;
    temp.push_back(x);
  }
  for (int i = temp.size() - 1; i >= 0; --i) {
    numbers.push_back(temp[i]);
  }
}
lint abs(lint number) {
  lint n(number);
  lint zero(0);
  bool is_less = n.cmp(zero);
  if (is_less) {
    n *= lint(-1);
  }
  return n;
}
lint pow(lint a, int n) {
  lint res(1);
  while (n) {
    if (n & 1) {
      res *= a;
    }
    a *= a;
    n >>= 1;
  }
  return res;
}
std::ostream& operator<<(std::ostream& os, const lint& obj) {
  if (obj.is_negative_number()) {
    os << "-";
  }
  for (int i = 0; i < obj.get_length(); ++i) {
    os << obj[i];
  }
  return os;
}
std::istream& operator>>(std::istream& is, lint& obj) {
  bool is_lead_zeros = true;
  bool is_negative = false;
  vector<int> numbers;
  while (is.good()) {
    char c = static_cast<char>(is.get());
    int ic = c - '0';
    if (c == '\n') {
      break;
    }
    if (c == EOF) {
      break;
    }
    if (c == '\0') {
      break;
    }
    if (is.good()) {
      if (c == '-') {
        is_negative = true;
      } else if (c == '+') {
        is_negative = false;
      } else if (ic == 0 && is_lead_zeros) {
      } else {
        numbers.push_back(ic);
        is_lead_zeros = false;
      }
    }
  }
  lint temp(numbers, is_negative);
  obj = temp;
  return is;
}
lint operator+(const lint& lhs, const lint& rhs) {
  lint temp(lhs);
  return temp += rhs;
}
lint operator-(const lint& lhs, const lint& rhs) {
  lint temp(lhs);
  return temp -= rhs;
}
lint operator*(const lint& lhs, const lint& rhs) {
  lint temp(lhs);
  return temp *= rhs;
}
lint operator/(const lint& lhs, const lint& rhs) {
  lint temp(lhs);
  return temp /= rhs;
}
}  // namespace apa
using namespace std;
const long long inf = 2e9;
template <typename t>
t gcd(t a, t b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename t>
long long pow(t a, t b) {
  if (b == 0) return 1;
  long long cur = pow(a, b / 2);
  if (b % 2 == 0)
    return (1ll * cur * cur) % 1000000007;
  else
    return (1ll * cur * cur * a) % 1000000007;
}
template <typename t>
bool isOk(t x, t y, t boundX, t boundY) {
  return ((x >= 0) && (y >= 0) && (x < boundX) && (y < boundY));
}
double square(vector<pair<double, double>> nodes) {
  double area = 0;
  int numPoints = nodes.size();
  int j = numPoints - 1;
  for (int i = 0; i < numPoints; i++) {
    area = area + (nodes[j].first + nodes[i].first) *
                      (nodes[j].second - nodes[i].second);
    j = i;
  }
  return area / 2;
}
struct PointF {
  double X;
  double Y;
  PointF(double x, double y) {
    X = x;
    Y = y;
  }
};
double distance(double x1, double y1, double x2, double y2) {
  return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
class FenwickTree {
 public:
  void updateBinaryIndexedTree(vector<int>& binaryIndexedTree, int val,
                               int index) {
    while (index < binaryIndexedTree.size()) {
      binaryIndexedTree[index] += val;
      index = getNext(index);
    }
  }
  int getSum(vector<int>& binaryIndexedTree, int index) {
    int sum = 0;
    while (index >= 0) {
      sum += binaryIndexedTree[index];
      index = getParent(index);
    }
    return sum;
  }
  int getParent(int i) { return (i & (i + 1)) - 1; }
  int getNext(int i) { return i | (i + 1); }
  static void test() {
    vector<int> input = {1, 2, 3, 4, 5, 6, 7};
    FenwickTree ft;
    vector<int> binaryIndexedTree(input.size() + 1, 0);
    for (int i = 0; i < input.size(); ++i) {
      ft.updateBinaryIndexedTree(binaryIndexedTree, input[i], i);
    }
    cout << (bool)(1 == (int)ft.getSum(binaryIndexedTree, 0));
    cout << (bool)(3 == (int)ft.getSum(binaryIndexedTree, 1));
    cout << (bool)(6 == (int)ft.getSum(binaryIndexedTree, 2));
    cout << (bool)(10 == (int)ft.getSum(binaryIndexedTree, 3));
    cout << (bool)(15 == (int)ft.getSum(binaryIndexedTree, 4));
    cout << (bool)(21 == (int)ft.getSum(binaryIndexedTree, 5));
    cout << (bool)(28 == (int)ft.getSum(binaryIndexedTree, 6));
  }
};
struct mp {
  mp(int _x, int _y) {
    x = _x;
    y = _y;
  }
  mp(){};
  long long x, y;
  friend bool operator<(mp rhs, mp another) {
    return (long long)(rhs.x + (long long)rhs.y * 5322) <
           (long long)(another.x + (long long)another.y * 5322);
  }
  friend bool operator==(mp rhs, mp another) {
    return (long long)(rhs.x + (long long)rhs.y * 5322) ==
           (long long)(another.x + (long long)another.y * 5322);
  }
};
long long bits[] = {
    1,         2,         4,          8,         16,       32,       64,
    128,       256,       512,        1024,      2048,     4096,     8192,
    16384,     32768,     65536,      131072,    262144,   524288,   1048576,
    2097152,   4194304,   8388608,    16777216,  33554432, 67108864, 134217728,
    268435456, 536870912, 1073741824, 2147483648};
long long factmod(long long n, long long p) {
  long long res = 1;
  while (n > 1) {
    res = (res * ((n / p) % 2 ? p - 1 : 1)) % p;
    for (int i = 2; i <= n % p; ++i) res = (res * i) % p;
    n /= p;
  }
  return res % p;
}
long long merged(long long a, long long b) { return a + b; }
struct SegTree {
  vector<long long> tree;
  vector<long long> lazy;
  int upbound;
  SegTree(int n) {
    int pow2 = 1;
    while (pow2 < n) {
      pow2 = (pow2 << 1);
    }
    tree.resize(pow2 * 2 - 1);
    for (int i = 0; i < tree.size(); ++i) {
      tree[i] = 0;
    }
    lazy.resize(pow2 * 2 - 1);
    upbound = n - 1;
  }

 public:
  void create(vector<long long>& input) {
    create(input, 0, input.size() - 1, 0);
  }
  long long query(int l, int r) { return query(l, r, 0, upbound, 0); }
  void update(int index, int delta) {
    updateSegmentTree(index, delta, 0, upbound, 0);
  }
  void updateRange(int l, int r, int delta) {
    updateRange(l, r, delta, 0, upbound, 0);
  }
  void updateLazy(int l, int r, int delta) {
    updateLazy(l, r, delta, 0, upbound, 0);
  }
  long long queryLazy(int l, int r) { return queryLazy(l, r, 0, upbound, 0); }

 private:
  void create(vector<long long>& input, int l, int r, int pos) {
    if (l == r) {
      tree[pos] = input[l];
      return;
    }
    int mid = (l + r) / 2;
    create(input, l, mid, 2 * pos + 1);
    create(input, mid + 1, r, 2 * pos + 2);
    tree[pos] = merged(tree[2 * pos + 1], tree[2 * pos + 2]);
  }
  long long query(int ql, int qr, int l, int r, int pos) {
    if (ql <= l && qr >= r) return tree[pos];
    if (ql > r || qr < l) {
      return 0;
    }
    int mid = (l + r) / 2;
    return merged(query(ql, qr, l, mid, pos * 2 + 1),
                  query(ql, qr, mid + 1, r, pos * 2 + 2));
  }
  void updateSegmentTree(int index, int delta, int low, int high, int pos) {
    if (index < low || index > high) {
      return;
    }
    if (low == high) {
      tree[pos] += delta;
      return;
    }
    int mid = (low + high) / 2;
    updateSegmentTree(index, delta, low, mid, 2 * pos + 1);
    updateSegmentTree(index, delta, mid + 1, high, 2 * pos + 2);
    tree[pos] = merged(tree[2 * pos + 1], tree[2 * pos + 2]);
  }
  void updateRange(int startRange, int endRange, int delta, int low, int high,
                   int pos) {
    if (low > high || startRange > high || endRange < low) {
      return;
    }
    if (low == high) {
      tree[pos] += delta;
      return;
    }
    int middle = (low + high) / 2;
    updateRange(startRange, endRange, delta, low, middle, 2 * pos + 1);
    updateRange(startRange, endRange, delta, middle + 1, high, 2 * pos + 2);
    tree[pos] = merged(tree[2 * pos + 1], tree[2 * pos + 2]);
  }
  void updateLazy(int startRange, int endRange, int delta, int low, int high,
                  int pos) {
    if (low > high) {
      return;
    }
    if (lazy[pos] != 0) {
      tree[pos] += lazy[pos];
      if (low != high) {
        lazy[2 * pos + 1] += lazy[pos];
        lazy[2 * pos] += lazy[pos];
      }
      lazy[pos] = 0;
    }
    if (startRange > high || endRange < low) {
      return;
    }
    if (startRange <= low && endRange >= high) {
      tree[pos] += delta;
      if (low != high) {
        lazy[2 * pos + 1] += delta;
        lazy[2 * pos] += delta;
      }
      return;
    }
    int mid = (low + high) / 2;
    updateLazy(startRange, endRange, delta, low, mid, 2 * pos + 1);
    updateLazy(startRange, endRange, delta, mid + 1, high, 2 * pos);
    tree[pos] = merged(tree[2 * pos + 1], tree[2 * pos]);
  }
  long long queryLazy(int qlow, int qhigh, int low, int high, int pos) {
    if (low > high) {
      return 0;
    }
    if (lazy[pos] != 0) {
      tree[pos] += lazy[pos];
      if (low != high) {
        lazy[2 * pos + 1] += lazy[pos];
        lazy[2 * pos] += lazy[pos];
      }
      lazy[pos] = 0;
    }
    if (qlow > high || qhigh < low) {
      return 0;
    }
    if (qlow <= low && qhigh >= high) {
      return tree[pos];
    }
    int mid = (low + high) / 2;
    return merged(queryLazy(qlow, qhigh, low, mid, 2 * pos),
                  queryLazy(qlow, qhigh, mid + 1, high, 2 * pos + 1));
  }

 public:
  static void test() {
    vector<long long> input = {0, 3, 4, 2, 1, 6, -1};
    SegTree tr(input.size());
    tr.create(input);
    cout << (bool)(0 == tr.query(0, 3)) << endl;
    cout << (bool)(1 == tr.query(1, 5)) << endl;
    cout << (bool)(-1 == tr.query(1, 6)) << endl;
    tr.update(2, 1);
    cout << (bool)(2 == tr.query(1, 3)) << endl;
    tr.updateRange(3, 5, -2);
    cout << (bool)(-1 == tr.query(5, 6)) << endl;
    cout << (bool)(0 == tr.query(0, 3)) << endl;
    vector<long long> input1 = {-1, 2, 4, 1, 7, 1, 3, 2};
    SegTree tr1(input1.size());
    tr1.create(input1);
    tr1.updateLazy(0, 3, 1);
    tr1.updateLazy(0, 0, 2);
    cout << (bool)(1 == tr1.queryLazy(3, 5)) << endl;
  }
};
struct vert {
  char type;
  int val;
  int index;
  vector<int> child;
};
vert g[2000001];
bitset<2000001> colors;
bool weirdDfs(int v) {
  auto ver = g[v];
  if (ver.type == 'I') {
    colors[v] = ver.val;
    return ver.val;
  } else {
    if (ver.type == 'A') {
      auto l = weirdDfs(g[v].child[0]);
      auto r = weirdDfs(g[v].child[1]);
      colors[v] = l & r;
      return l & r;
    }
    if (ver.type == 'N') {
      colors[v] = !weirdDfs(g[v].child[0]);
      return colors[v];
    }
    if (ver.type == 'X') {
      auto l = weirdDfs(g[v].child[0]);
      auto r = weirdDfs(g[v].child[1]);
      colors[v] = l ^ r;
      return colors[v];
    }
    if (ver.type == 'O') {
      auto l = weirdDfs(g[v].child[0]);
      auto r = weirdDfs(g[v].child[1]);
      colors[v] = l | r;
      return colors[v];
    }
  }
}
bitset<2000001> rev;
void dfs(int v, bool b) {
  if (v == 0) {
    rev[v] = 1;
  }
  auto ver = g[v];
  bool next = false;
  if (b) {
    if (ver.type == 'X') {
      auto l = g[ver.child[0]];
      auto r = g[ver.child[1]];
      bool checkl =
          ((!colors[l.index]) ^ (colors[r.index])) != colors[ver.index];
      bool checkr =
          ((colors[l.index]) ^ (!colors[r.index])) != colors[ver.index];
      rev[l.index] = checkl;
      rev[r.index] = checkr;
      dfs(l.index, checkl);
      dfs(r.index, checkr);
    }
    if (ver.type == 'A') {
      auto l = g[ver.child[0]];
      auto r = g[ver.child[1]];
      bool checkl =
          ((!colors[l.index]) & (colors[r.index])) != colors[ver.index];
      bool checkr =
          ((colors[l.index]) & (!colors[r.index])) != colors[ver.index];
      rev[l.index] = checkl;
      rev[r.index] = checkr;
      dfs(l.index, checkl);
      dfs(r.index, checkr);
    }
    if (ver.type == 'O') {
      auto l = g[ver.child[0]];
      auto r = g[ver.child[1]];
      bool checkl =
          ((!colors[l.index]) | (colors[r.index])) != colors[ver.index];
      bool checkr =
          ((colors[l.index]) | (!colors[r.index])) != colors[ver.index];
      rev[l.index] = checkl;
      rev[r.index] = checkr;
      dfs(l.index, checkl);
      dfs(r.index, checkr);
    }
    if (ver.type == 'N') {
      auto l = g[ver.child[0]];
      rev[l.index] = true;
      dfs(l.index, true);
    }
    if (ver.type == 'I') {
      return;
    }
  } else {
    next = false;
    for (auto i : g[v].child) {
      rev[i] = false;
    }
    for (auto i : g[v].child) {
      dfs(i, next);
    }
  }
}
char getChar(string s) { return s[0]; }
void solvec() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    vert v;
    int t1, t2;
    string t;
    cin >> t;
    v.type = getChar(t);
    if (t == "IN") {
      cin >> v.val;
    } else if (t == "NOT") {
      cin >> t1;
      --t1;
      v.child.emplace_back(t1);
    } else {
      cin >> t1 >> t2;
      --t1;
      --t2;
      v.child.emplace_back(t1);
      v.child.emplace_back(t2);
    }
    v.index = i;
    g[i] = (v);
  }
  weirdDfs(0);
  dfs(0, true);
  for (int i = 0; i < n; ++i) {
    if (g[i].type == 'I') {
      if (rev[i]) {
        cout << !colors[0];
      } else {
        cout << colors[0];
      }
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  double beg = clock();
  int n = 1;
  for (int i = 0; i < n; ++i) {
    solvec();
    return 0;
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Natasha travels around Mars in the Mars rover. But suddenly it broke down, namely — the logical scheme inside it. The scheme is an undirected tree (connected acyclic graph) with a root in the vertex 1, in which every leaf (excluding root) is an input, and all other vertices are logical elements, including the root, which is output. One bit is fed to each input. One bit is returned at the output.

There are four types of logical elements: [AND](https://en.wikipedia.org/wiki/Logical_conjunction) (2 inputs), [OR](https://en.wikipedia.org/wiki/Logical_disjunction) (2 inputs), [XOR](https://en.wikipedia.org/wiki/Exclusive_or) (2 inputs), [NOT](https://en.wikipedia.org/wiki/Negation) (1 input). Logical elements take values from their direct descendants (inputs) and return the result of the function they perform. Natasha knows the logical scheme of the Mars rover, as well as the fact that only one input is broken. In order to fix the Mars rover, she needs to change the value on this input.

For each input, determine what the output will be if Natasha changes this input.

Input

The first line contains a single integer n (2 ≤ n ≤ 10^6) — the number of vertices in the graph (both inputs and elements).

The i-th of the next n lines contains a description of i-th vertex: the first word "AND", "OR", "XOR", "NOT" or "IN" (means the input of the scheme) is the vertex type. If this vertex is "IN", then the value of this input follows (0 or 1), otherwise follow the indices of input vertices of this element: "AND", "OR", "XOR" have 2 inputs, whereas "NOT" has 1 input. The vertices are numbered from one.

It is guaranteed that input data contains a correct logical scheme with an output produced by the vertex 1.

Output

Print a string of characters '0' and '1' (without quotes) — answers to the problem for each input in the ascending order of their vertex indices.

Example

Input

10
AND 9 4
IN 1
IN 1
XOR 6 5
AND 3 7
IN 0
NOT 10
IN 1
IN 1
AND 2 8


Output

10110

Note

The original scheme from the example (before the input is changed):

<image>

Green indicates bits '1', yellow indicates bits '0'.

If Natasha changes the input bit 2 to 0, then the output will be 1.

If Natasha changes the input bit 3 to 0, then the output will be 0.

If Natasha changes the input bit 6 to 1, then the output will be 1.

If Natasha changes the input bit 8 to 0, then the output will be 1.

If Natasha changes the input bit 9 to 0, then the output will be 0.

### Response

```cpp
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
namespace apa {
using namespace std;
template <typename T>
class ComparisonOperators {
  friend bool operator==(T const& lhs, T const& rhs) {
    return lhs.compare(rhs) == 0;
  }
  friend bool operator!=(T const& lhs, T const& rhs) {
    return lhs.compare(rhs) != 0;
  }
  friend bool operator<(T const& lhs, T const& rhs) {
    return lhs.compare(rhs) < 0;
  }
  friend bool operator>(T const& lhs, T const& rhs) {
    return rhs.compare(lhs) < 0;
  }
  friend bool operator<=(T const& lhs, T const& rhs) {
    bool result = lhs.compare(rhs) <= 0;
    return result;
  }
  friend bool operator>=(T const& lhs, T const& rhs) {
    return rhs.compare(lhs) <= 0;
  }
};
class lint : ComparisonOperators<lint> {
 public:
  explicit lint(std::string number);
  lint();
  lint(long long number);
  lint(int number);
  lint(double number);
  lint(vector<int> nums, bool is_neg);
  lint(const lint& obj);
  int get_length() const;
  bool is_negative_number() const;
  lint& operator+=(const lint& b);
  lint& operator-=(const lint& b);
  lint& operator*=(const lint& number2);
  lint& operator/=(const lint& b);
  explicit operator bool() const;
  explicit operator int();
  lint operator+() const;
  lint operator-() const;
  int operator[](size_t index) const;
  lint& operator=(const lint& other);
  lint& operator++();
  lint operator++(int);
  lint& operator--();
  lint operator--(int);
  bool cmp(lint const& rhs) const;
  int compare(lint const& rhs) const;
  bool is_zero() const;
  std::string to_string();

 private:
  bool is_negative;
  vector<int> numbers;
  lint abs(lint number) const;
  vector<int> reverse_numbers(vector<int> const& numbers) const;
  void make_equal_length(const lint& b, vector<int>& number1,
                         vector<int>& number2) const;
  void string_to_vector(std::string const& number);
  void integer_to_vector(long long a);
};
lint abs(lint number);
lint pow(lint a, int n);
std::ostream& operator<<(std::ostream& os, const lint& obj);
std::istream& operator>>(std::istream& is, lint& obj);
lint operator+(const lint& lhs, const lint& rhs);
lint operator-(const lint& lhs, const lint& rhs);
lint operator*(const lint& lhs, const lint& rhs);
lint operator/(const lint& lhs, const lint& rhs);
}  // namespace apa
namespace apa {
lint::lint(std::string number) { string_to_vector(number); }
lint::lint() { integer_to_vector(0); }
lint::lint(long long number) { integer_to_vector(number); }
lint::lint(int number) { integer_to_vector(static_cast<long long>(number)); }
lint::lint(double number) {
  std::string str = std::to_string(std::trunc(number));
  std::string result = str.substr(0, str.size() - 7);
  string_to_vector(result);
}
lint::lint(vector<int> nums, bool is_neg) {
  numbers = nums;
  is_negative = is_neg;
}
lint::lint(const lint& obj) {
  is_negative = obj.is_negative_number();
  for (int t : obj.numbers) {
    numbers.push_back(t);
  }
}
int lint::get_length() const { return numbers.size(); }
bool lint::is_negative_number() const { return is_negative; }
lint& lint::operator+=(const lint& b) {
  if (!is_negative_number() && b.is_negative_number()) {
    lint temp(b);
    temp = abs(temp);
    return operator-=(temp);
  }
  if (is_negative_number() && !b.is_negative_number()) {
    lint temp_this = lint(*this);
    temp_this.is_negative = false;
    lint temp = lint(b);
    temp -= temp_this;
    *this = temp;
    return *this;
  }
  vector<int> number1;
  vector<int> number2;
  make_equal_length(b, number1, number2);
  vector<int> result;
  int rest = 0;
  for (int i = number1.size() - 1; i >= 0; --i) {
    int sum = number1[i] + number2[i] + rest;
    if (sum > 9) {
      rest = 1;
      sum -= 10;
    } else {
      rest = 0;
    }
    result.push_back(sum);
  }
  if (rest > 0) {
    result.push_back(rest);
  }
  vector<int> reverse_result = reverse_numbers(result);
  (*this).numbers = reverse_result;
  return *this;
}
lint& lint::operator-=(const lint& b) {
  if (!is_negative_number() && b.is_negative_number()) {
    return (*this).operator+=(abs(b));
  }
  if (is_negative_number() && !b.is_negative_number()) {
    lint temp(b);
    temp.is_negative = true;
    return (*this).operator+=(temp);
  }
  vector<int> number1;
  vector<int> number2;
  make_equal_length(b, number1, number2);
  int is_number1_more_than_number2 = 0;
  for (unsigned int i = 0; i < number1.size(); ++i) {
    if (number1[i] > number2[i]) {
      is_number1_more_than_number2 = 1;
      break;
    } else if (number1[i] < number2[i]) {
      is_number1_more_than_number2 = 2;
      break;
    }
  }
  if (is_number1_more_than_number2 == 0) {
    vector<int> t;
    t.push_back(0);
    numbers = t;
    return *this;
  }
  vector<int> result;
  if (is_number1_more_than_number2 == 1) {
    for (int i = number1.size() - 1; i >= 0; --i) {
      if (number1[i] < number2[i]) {
        number1[i] += 10;
        number1[i - 1] -= 1;
      }
      int r = number1[i] - number2[i];
      result.push_back(r);
    }
  } else if (is_number1_more_than_number2 == 2) {
    for (int i = number2.size() - 1; i >= 0; --i) {
      if (number2[i] < number1[i]) {
        number2[i] += 10;
        number2[i - 1] -= 1;
      }
      int r = number2[i] - number1[i];
      result.push_back(r);
    }
  }
  bool can_copy = false;
  vector<int> result_without_zero;
  for (int i = result.size() - 1; i >= 0; --i) {
    if (result[i] != 0) {
      can_copy = true;
    }
    if (can_copy) {
      result_without_zero.push_back(result[i]);
    }
  }
  (*this).numbers = result_without_zero;
  if (!is_negative_number() && !b.is_negative_number()) {
    if (is_number1_more_than_number2 == 2) {
      is_negative = true;
    }
  }
  if (is_negative_number() && b.is_negative_number()) {
    if (is_number1_more_than_number2 == 2) {
      is_negative = false;
    }
  }
  return *this;
}
lint& lint::operator*=(const lint& number2) {
  vector<int> a = reverse_numbers(numbers);
  vector<int> b = reverse_numbers(number2.numbers);
  vector<int> c(a.size() + b.size(), 0);
  for (size_t i = 0; i < a.size(); ++i) {
    int carry = 0;
    for (unsigned int j = 0; j < b.size() || carry; ++j) {
      long long cur = c[i + j] + a[i] * 1ll * (j < b.size() ? b[j] : 0) + carry;
      c[i + j] = int(cur % 10);
      carry = int(cur / 10);
    }
  }
  while (c.size() > 1 && c.back() == 0) {
    c.pop_back();
  }
  vector<int> result = reverse_numbers(c);
  numbers = result;
  if (is_negative_number() && !number2.is_negative_number()) {
    is_negative = true;
  } else if (!is_negative_number() && number2.is_negative_number()) {
    is_negative = true;
  } else {
    is_negative = false;
  }
  return *this;
}
lint& lint::operator/=(const lint& number2) {
  if (number2.is_zero()) {
    int d = 4 - 4;
    int a = 4 / d;
    numbers.push_back(a);
  }
  if (is_zero()) {
    vector<int> temp;
    temp.push_back(0);
    numbers = temp;
    is_negative = false;
    return *this;
  }
  bool second_number_more_then_first_number = abs(*this).cmp(abs(number2));
  if (second_number_more_then_first_number) {
    vector<int> temp;
    temp.push_back(0);
    numbers = temp;
    is_negative = false;
    return *this;
  }
  vector<int> res;
  for (int i = (*this).get_length() - 1; i >= 0; --i) {
    res.push_back(0);
  }
  lint current_value(0);
  for (int i = 0; i < (*this).get_length(); ++i) {
    current_value = current_value * 10;
    current_value.numbers[current_value.get_length() - 1] = (*this).numbers[i];
    int x = 0;
    int left_index = 0;
    int right_index = 10;
    while (left_index <= right_index) {
      int middle = (left_index + right_index) >> 1;
      lint cur = abs(number2) * middle;
      if (abs(cur) <= abs(current_value)) {
        x = middle;
        left_index = middle + 1;
      } else {
        right_index = middle - 1;
      }
    }
    res[i] = x;
    current_value = current_value - abs(number2) * x;
  }
  res = reverse_numbers(res);
  while (res.size() > 1 && res.back() == 0) {
    res.pop_back();
  }
  res = reverse_numbers(res);
  numbers = res;
  if (is_negative_number() && !number2.is_negative_number()) {
    is_negative = true;
  } else if (!is_negative_number() && number2.is_negative_number()) {
    is_negative = true;
  } else {
    is_negative = false;
  }
  return *this;
}
lint::operator bool() const { return !is_zero(); }
lint::operator int() { return std::stoi((*this).to_string()); }
lint lint::operator+() const {
  lint temp(*this);
  return temp;
}
lint lint::operator-() const {
  lint temp(*this);
  if (is_negative_number()) {
    temp.is_negative = false;
  } else {
    temp.is_negative = true;
  }
  return temp;
}
int lint::operator[](size_t index) const { return numbers[index]; }
lint& lint::operator=(const lint& other) {
  if (this != &other) {
    numbers = other.numbers;
    is_negative = other.is_negative_number();
  }
  return *this;
}
lint& lint::operator++() {
  lint one(1);
  (*this) += one;
  return *this;
}
lint lint::operator++(int) {
  lint tmp(*this);
  operator++();
  return tmp;
}
lint& lint::operator--() {
  lint one(1);
  (*this) -= one;
  return *this;
}
lint lint::operator--(int) {
  lint tmp(*this);
  operator--();
  return tmp;
}
bool lint::cmp(lint const& rhs) const {
  if (is_negative_number() && !rhs.is_negative_number()) {
    return true;
  }
  if (!is_negative_number() && rhs.is_negative_number()) {
    return false;
  }
  if (get_length() < rhs.get_length()) {
    return true;
  }
  if (get_length() > rhs.get_length()) {
    return false;
  }
  for (int i = 0; i < get_length(); ++i) {
    if (numbers[i] < rhs[i]) {
      if (is_negative_number()) {
        return false;
      }
      return true;
    } else if (numbers[i] > rhs[i]) {
      if (is_negative_number()) {
        return true;
      }
      return false;
    }
  }
  return false;
}
int lint::compare(lint const& rhs) const {
  if ((*this).cmp(rhs)) {
    return -1;
  } else if (rhs.cmp(*this)) {
    return 1;
  } else {
    return 0;
  }
}
lint lint::abs(lint number) const {
  number.is_negative = false;
  return number;
}
bool lint::is_zero() const {
  if (numbers.size() == 1 && numbers[0] == 0) {
    return true;
  }
  return false;
}
std::string int_to_string(int i) {
  std::stringstream ss;
  std::string s;
  ss << i;
  s = ss.str();
  return s;
}
std::string lint::to_string() {
  std::string result = "";
  if (is_negative_number() && !is_zero()) {
    result += "-";
  }
  for (int i = 0; i < get_length(); ++i) {
    int a = (*this)[i];
    result += int_to_string(a);
  }
  return result;
}
vector<int> lint::reverse_numbers(vector<int> const& numbers) const {
  vector<int> reverse_result;
  for (int i = numbers.size() - 1; i >= 0; --i) {
    reverse_result.push_back(numbers[i]);
  }
  return reverse_result;
}
void lint::make_equal_length(lint const& b, vector<int>& number1,
                             vector<int>& number2) const {
  int diff_length = get_length() - b.get_length();
  if (diff_length > 0) {
    number1 = (*this).numbers;
    for (int i = 0; i < diff_length; ++i) {
      number2.push_back(0);
    }
    for (int i = 0; i < b.get_length(); ++i) {
      number2.push_back(b[i]);
    }
  } else if (diff_length < 0) {
    for (int i = 0; i < b.get_length(); ++i) {
      number2.push_back(b[i]);
    }
    for (int i = 0; i < (diff_length * (-1)); ++i) {
      number1.push_back(0);
    }
    for (int i = 0; i < get_length(); ++i) {
      number1.push_back((*this)[i]);
    }
  } else {
    for (int i = 0; i < b.get_length(); ++i) {
      number1.push_back((*this)[i]);
      number2.push_back(b[i]);
    }
  }
}
void lint::string_to_vector(std::string const& number) {
  unsigned int from = 0;
  if (number[0] == '-') {
    is_negative = true;
    from = 1;
  } else {
    is_negative = false;
  }
  for (unsigned int i = from; i < number.length(); ++i) {
    int ia = number[i] - '0';
    numbers.push_back(ia);
  }
}
void lint::integer_to_vector(long long a) {
  if (a < 0) {
    is_negative = true;
    a = (-1) * a;
  } else {
    is_negative = false;
  }
  if (a == 0) {
    numbers.push_back(0);
  }
  vector<int> temp;
  while (a) {
    int x = a % 10;
    a /= 10;
    temp.push_back(x);
  }
  for (int i = temp.size() - 1; i >= 0; --i) {
    numbers.push_back(temp[i]);
  }
}
lint abs(lint number) {
  lint n(number);
  lint zero(0);
  bool is_less = n.cmp(zero);
  if (is_less) {
    n *= lint(-1);
  }
  return n;
}
lint pow(lint a, int n) {
  lint res(1);
  while (n) {
    if (n & 1) {
      res *= a;
    }
    a *= a;
    n >>= 1;
  }
  return res;
}
std::ostream& operator<<(std::ostream& os, const lint& obj) {
  if (obj.is_negative_number()) {
    os << "-";
  }
  for (int i = 0; i < obj.get_length(); ++i) {
    os << obj[i];
  }
  return os;
}
std::istream& operator>>(std::istream& is, lint& obj) {
  bool is_lead_zeros = true;
  bool is_negative = false;
  vector<int> numbers;
  while (is.good()) {
    char c = static_cast<char>(is.get());
    int ic = c - '0';
    if (c == '\n') {
      break;
    }
    if (c == EOF) {
      break;
    }
    if (c == '\0') {
      break;
    }
    if (is.good()) {
      if (c == '-') {
        is_negative = true;
      } else if (c == '+') {
        is_negative = false;
      } else if (ic == 0 && is_lead_zeros) {
      } else {
        numbers.push_back(ic);
        is_lead_zeros = false;
      }
    }
  }
  lint temp(numbers, is_negative);
  obj = temp;
  return is;
}
lint operator+(const lint& lhs, const lint& rhs) {
  lint temp(lhs);
  return temp += rhs;
}
lint operator-(const lint& lhs, const lint& rhs) {
  lint temp(lhs);
  return temp -= rhs;
}
lint operator*(const lint& lhs, const lint& rhs) {
  lint temp(lhs);
  return temp *= rhs;
}
lint operator/(const lint& lhs, const lint& rhs) {
  lint temp(lhs);
  return temp /= rhs;
}
}  // namespace apa
using namespace std;
const long long inf = 2e9;
template <typename t>
t gcd(t a, t b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename t>
long long pow(t a, t b) {
  if (b == 0) return 1;
  long long cur = pow(a, b / 2);
  if (b % 2 == 0)
    return (1ll * cur * cur) % 1000000007;
  else
    return (1ll * cur * cur * a) % 1000000007;
}
template <typename t>
bool isOk(t x, t y, t boundX, t boundY) {
  return ((x >= 0) && (y >= 0) && (x < boundX) && (y < boundY));
}
double square(vector<pair<double, double>> nodes) {
  double area = 0;
  int numPoints = nodes.size();
  int j = numPoints - 1;
  for (int i = 0; i < numPoints; i++) {
    area = area + (nodes[j].first + nodes[i].first) *
                      (nodes[j].second - nodes[i].second);
    j = i;
  }
  return area / 2;
}
struct PointF {
  double X;
  double Y;
  PointF(double x, double y) {
    X = x;
    Y = y;
  }
};
double distance(double x1, double y1, double x2, double y2) {
  return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
class FenwickTree {
 public:
  void updateBinaryIndexedTree(vector<int>& binaryIndexedTree, int val,
                               int index) {
    while (index < binaryIndexedTree.size()) {
      binaryIndexedTree[index] += val;
      index = getNext(index);
    }
  }
  int getSum(vector<int>& binaryIndexedTree, int index) {
    int sum = 0;
    while (index >= 0) {
      sum += binaryIndexedTree[index];
      index = getParent(index);
    }
    return sum;
  }
  int getParent(int i) { return (i & (i + 1)) - 1; }
  int getNext(int i) { return i | (i + 1); }
  static void test() {
    vector<int> input = {1, 2, 3, 4, 5, 6, 7};
    FenwickTree ft;
    vector<int> binaryIndexedTree(input.size() + 1, 0);
    for (int i = 0; i < input.size(); ++i) {
      ft.updateBinaryIndexedTree(binaryIndexedTree, input[i], i);
    }
    cout << (bool)(1 == (int)ft.getSum(binaryIndexedTree, 0));
    cout << (bool)(3 == (int)ft.getSum(binaryIndexedTree, 1));
    cout << (bool)(6 == (int)ft.getSum(binaryIndexedTree, 2));
    cout << (bool)(10 == (int)ft.getSum(binaryIndexedTree, 3));
    cout << (bool)(15 == (int)ft.getSum(binaryIndexedTree, 4));
    cout << (bool)(21 == (int)ft.getSum(binaryIndexedTree, 5));
    cout << (bool)(28 == (int)ft.getSum(binaryIndexedTree, 6));
  }
};
struct mp {
  mp(int _x, int _y) {
    x = _x;
    y = _y;
  }
  mp(){};
  long long x, y;
  friend bool operator<(mp rhs, mp another) {
    return (long long)(rhs.x + (long long)rhs.y * 5322) <
           (long long)(another.x + (long long)another.y * 5322);
  }
  friend bool operator==(mp rhs, mp another) {
    return (long long)(rhs.x + (long long)rhs.y * 5322) ==
           (long long)(another.x + (long long)another.y * 5322);
  }
};
long long bits[] = {
    1,         2,         4,          8,         16,       32,       64,
    128,       256,       512,        1024,      2048,     4096,     8192,
    16384,     32768,     65536,      131072,    262144,   524288,   1048576,
    2097152,   4194304,   8388608,    16777216,  33554432, 67108864, 134217728,
    268435456, 536870912, 1073741824, 2147483648};
long long factmod(long long n, long long p) {
  long long res = 1;
  while (n > 1) {
    res = (res * ((n / p) % 2 ? p - 1 : 1)) % p;
    for (int i = 2; i <= n % p; ++i) res = (res * i) % p;
    n /= p;
  }
  return res % p;
}
long long merged(long long a, long long b) { return a + b; }
struct SegTree {
  vector<long long> tree;
  vector<long long> lazy;
  int upbound;
  SegTree(int n) {
    int pow2 = 1;
    while (pow2 < n) {
      pow2 = (pow2 << 1);
    }
    tree.resize(pow2 * 2 - 1);
    for (int i = 0; i < tree.size(); ++i) {
      tree[i] = 0;
    }
    lazy.resize(pow2 * 2 - 1);
    upbound = n - 1;
  }

 public:
  void create(vector<long long>& input) {
    create(input, 0, input.size() - 1, 0);
  }
  long long query(int l, int r) { return query(l, r, 0, upbound, 0); }
  void update(int index, int delta) {
    updateSegmentTree(index, delta, 0, upbound, 0);
  }
  void updateRange(int l, int r, int delta) {
    updateRange(l, r, delta, 0, upbound, 0);
  }
  void updateLazy(int l, int r, int delta) {
    updateLazy(l, r, delta, 0, upbound, 0);
  }
  long long queryLazy(int l, int r) { return queryLazy(l, r, 0, upbound, 0); }

 private:
  void create(vector<long long>& input, int l, int r, int pos) {
    if (l == r) {
      tree[pos] = input[l];
      return;
    }
    int mid = (l + r) / 2;
    create(input, l, mid, 2 * pos + 1);
    create(input, mid + 1, r, 2 * pos + 2);
    tree[pos] = merged(tree[2 * pos + 1], tree[2 * pos + 2]);
  }
  long long query(int ql, int qr, int l, int r, int pos) {
    if (ql <= l && qr >= r) return tree[pos];
    if (ql > r || qr < l) {
      return 0;
    }
    int mid = (l + r) / 2;
    return merged(query(ql, qr, l, mid, pos * 2 + 1),
                  query(ql, qr, mid + 1, r, pos * 2 + 2));
  }
  void updateSegmentTree(int index, int delta, int low, int high, int pos) {
    if (index < low || index > high) {
      return;
    }
    if (low == high) {
      tree[pos] += delta;
      return;
    }
    int mid = (low + high) / 2;
    updateSegmentTree(index, delta, low, mid, 2 * pos + 1);
    updateSegmentTree(index, delta, mid + 1, high, 2 * pos + 2);
    tree[pos] = merged(tree[2 * pos + 1], tree[2 * pos + 2]);
  }
  void updateRange(int startRange, int endRange, int delta, int low, int high,
                   int pos) {
    if (low > high || startRange > high || endRange < low) {
      return;
    }
    if (low == high) {
      tree[pos] += delta;
      return;
    }
    int middle = (low + high) / 2;
    updateRange(startRange, endRange, delta, low, middle, 2 * pos + 1);
    updateRange(startRange, endRange, delta, middle + 1, high, 2 * pos + 2);
    tree[pos] = merged(tree[2 * pos + 1], tree[2 * pos + 2]);
  }
  void updateLazy(int startRange, int endRange, int delta, int low, int high,
                  int pos) {
    if (low > high) {
      return;
    }
    if (lazy[pos] != 0) {
      tree[pos] += lazy[pos];
      if (low != high) {
        lazy[2 * pos + 1] += lazy[pos];
        lazy[2 * pos] += lazy[pos];
      }
      lazy[pos] = 0;
    }
    if (startRange > high || endRange < low) {
      return;
    }
    if (startRange <= low && endRange >= high) {
      tree[pos] += delta;
      if (low != high) {
        lazy[2 * pos + 1] += delta;
        lazy[2 * pos] += delta;
      }
      return;
    }
    int mid = (low + high) / 2;
    updateLazy(startRange, endRange, delta, low, mid, 2 * pos + 1);
    updateLazy(startRange, endRange, delta, mid + 1, high, 2 * pos);
    tree[pos] = merged(tree[2 * pos + 1], tree[2 * pos]);
  }
  long long queryLazy(int qlow, int qhigh, int low, int high, int pos) {
    if (low > high) {
      return 0;
    }
    if (lazy[pos] != 0) {
      tree[pos] += lazy[pos];
      if (low != high) {
        lazy[2 * pos + 1] += lazy[pos];
        lazy[2 * pos] += lazy[pos];
      }
      lazy[pos] = 0;
    }
    if (qlow > high || qhigh < low) {
      return 0;
    }
    if (qlow <= low && qhigh >= high) {
      return tree[pos];
    }
    int mid = (low + high) / 2;
    return merged(queryLazy(qlow, qhigh, low, mid, 2 * pos),
                  queryLazy(qlow, qhigh, mid + 1, high, 2 * pos + 1));
  }

 public:
  static void test() {
    vector<long long> input = {0, 3, 4, 2, 1, 6, -1};
    SegTree tr(input.size());
    tr.create(input);
    cout << (bool)(0 == tr.query(0, 3)) << endl;
    cout << (bool)(1 == tr.query(1, 5)) << endl;
    cout << (bool)(-1 == tr.query(1, 6)) << endl;
    tr.update(2, 1);
    cout << (bool)(2 == tr.query(1, 3)) << endl;
    tr.updateRange(3, 5, -2);
    cout << (bool)(-1 == tr.query(5, 6)) << endl;
    cout << (bool)(0 == tr.query(0, 3)) << endl;
    vector<long long> input1 = {-1, 2, 4, 1, 7, 1, 3, 2};
    SegTree tr1(input1.size());
    tr1.create(input1);
    tr1.updateLazy(0, 3, 1);
    tr1.updateLazy(0, 0, 2);
    cout << (bool)(1 == tr1.queryLazy(3, 5)) << endl;
  }
};
struct vert {
  char type;
  int val;
  int index;
  vector<int> child;
};
vert g[2000001];
bitset<2000001> colors;
bool weirdDfs(int v) {
  auto ver = g[v];
  if (ver.type == 'I') {
    colors[v] = ver.val;
    return ver.val;
  } else {
    if (ver.type == 'A') {
      auto l = weirdDfs(g[v].child[0]);
      auto r = weirdDfs(g[v].child[1]);
      colors[v] = l & r;
      return l & r;
    }
    if (ver.type == 'N') {
      colors[v] = !weirdDfs(g[v].child[0]);
      return colors[v];
    }
    if (ver.type == 'X') {
      auto l = weirdDfs(g[v].child[0]);
      auto r = weirdDfs(g[v].child[1]);
      colors[v] = l ^ r;
      return colors[v];
    }
    if (ver.type == 'O') {
      auto l = weirdDfs(g[v].child[0]);
      auto r = weirdDfs(g[v].child[1]);
      colors[v] = l | r;
      return colors[v];
    }
  }
}
bitset<2000001> rev;
void dfs(int v, bool b) {
  if (v == 0) {
    rev[v] = 1;
  }
  auto ver = g[v];
  bool next = false;
  if (b) {
    if (ver.type == 'X') {
      auto l = g[ver.child[0]];
      auto r = g[ver.child[1]];
      bool checkl =
          ((!colors[l.index]) ^ (colors[r.index])) != colors[ver.index];
      bool checkr =
          ((colors[l.index]) ^ (!colors[r.index])) != colors[ver.index];
      rev[l.index] = checkl;
      rev[r.index] = checkr;
      dfs(l.index, checkl);
      dfs(r.index, checkr);
    }
    if (ver.type == 'A') {
      auto l = g[ver.child[0]];
      auto r = g[ver.child[1]];
      bool checkl =
          ((!colors[l.index]) & (colors[r.index])) != colors[ver.index];
      bool checkr =
          ((colors[l.index]) & (!colors[r.index])) != colors[ver.index];
      rev[l.index] = checkl;
      rev[r.index] = checkr;
      dfs(l.index, checkl);
      dfs(r.index, checkr);
    }
    if (ver.type == 'O') {
      auto l = g[ver.child[0]];
      auto r = g[ver.child[1]];
      bool checkl =
          ((!colors[l.index]) | (colors[r.index])) != colors[ver.index];
      bool checkr =
          ((colors[l.index]) | (!colors[r.index])) != colors[ver.index];
      rev[l.index] = checkl;
      rev[r.index] = checkr;
      dfs(l.index, checkl);
      dfs(r.index, checkr);
    }
    if (ver.type == 'N') {
      auto l = g[ver.child[0]];
      rev[l.index] = true;
      dfs(l.index, true);
    }
    if (ver.type == 'I') {
      return;
    }
  } else {
    next = false;
    for (auto i : g[v].child) {
      rev[i] = false;
    }
    for (auto i : g[v].child) {
      dfs(i, next);
    }
  }
}
char getChar(string s) { return s[0]; }
void solvec() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    vert v;
    int t1, t2;
    string t;
    cin >> t;
    v.type = getChar(t);
    if (t == "IN") {
      cin >> v.val;
    } else if (t == "NOT") {
      cin >> t1;
      --t1;
      v.child.emplace_back(t1);
    } else {
      cin >> t1 >> t2;
      --t1;
      --t2;
      v.child.emplace_back(t1);
      v.child.emplace_back(t2);
    }
    v.index = i;
    g[i] = (v);
  }
  weirdDfs(0);
  dfs(0, true);
  for (int i = 0; i < n; ++i) {
    if (g[i].type == 'I') {
      if (rev[i]) {
        cout << !colors[0];
      } else {
        cout << colors[0];
      }
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  double beg = clock();
  int n = 1;
  for (int i = 0; i < n; ++i) {
    solvec();
    return 0;
  }
  return 0;
}

```