#include <bits/stdc++.h>
using namespace std;
int n, q;
struct tree {
  int siz;
  long long min0, min1, r, tag;
  void update(long long v) {
    if (siz & 1) r += v;
    tag += v;
    min0 += v;
  }
} t[1000010], ans;
tree operator+(const tree &x, const tree &y) {
  tree o;
  o.tag = 0;
  o.siz = x.siz + y.siz;
  if (y.siz & 1)
    o.r = y.r - x.r;
  else
    o.r = y.r + x.r;
  if (x.siz & 1) {
    o.min0 = min(x.min0, y.min1 + x.r);
    o.min1 = min(x.min1, y.min0 - x.r);
  } else {
    o.min0 = min(x.min0, y.min0 - x.r);
    o.min1 = min(x.min1, y.min1 + x.r);
  }
  return o;
}
void build(int rex, int l, int r) {
  if (l == r) {
    int x;
    scanf("%d", &x);
    t[rex] = (tree){1, x - 1, 1ll << 60, x - 1, 0};
    return;
  }
  int mid = (l + r) >> 1;
  build(rex + rex, l, mid);
  build(rex + rex + 1, mid + 1, r);
  t[rex] = t[rex + rex] + t[rex + rex + 1];
}
void pushdown(int rex) {
  if (t[rex].tag) {
    t[rex + rex].update(t[rex].tag);
    t[rex + rex + 1].update(t[rex].tag);
    t[rex].tag = 0;
  }
}
void ins(int rex, int l, int r, int x, int y, int v) {
  if (l == x && r == y) {
    t[rex].update(v);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(rex);
  if (y <= mid)
    ins(rex + rex, l, mid, x, y, v);
  else if (x > mid)
    ins(rex + rex + 1, mid + 1, r, x, y, v);
  else
    ins(rex + rex, l, mid, x, mid, v),
        ins(rex + rex + 1, mid + 1, r, mid + 1, y, v);
  t[rex] = t[rex + rex] + t[rex + rex + 1];
}
void query(int rex, int l, int r, int x, int y) {
  if (l == x && r == y) {
    ans = ans + t[rex];
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(rex);
  if (y <= mid)
    query(rex + rex, l, mid, x, y);
  else if (x > mid)
    query(rex + rex + 1, mid + 1, r, x, y);
  else
    query(rex + rex, l, mid, x, mid),
        query(rex + rex + 1, mid + 1, r, mid + 1, y);
}
int main() {
  scanf("%d", &n);
  build(1, 1, n);
  scanf("%d", &q);
  while (q--) {
    int cas, l, r, k;
    scanf("%d%d%d", &cas, &l, &r);
    l++, r++;
    if (cas == 1) {
      scanf("%d", &k);
      ins(1, 1, n, l, r, k);
    } else {
      ans = (tree){0, 1ll < 60, 1ll << 60, 0, 0};
      query(1, 1, n, l, r);
      puts(!ans.r && ans.min0 >= 0 && ans.min1 >= 0 ? "1" : "0");
    }
  }
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

I’m strolling on sunshine, yeah-ah! And doesn’t it feel good! Well, it certainly feels good for our Heroes of Making Magic, who are casually walking on a one-directional road, fighting imps. Imps are weak and feeble creatures and they are not good at much. However, Heroes enjoy fighting them. For fun, if nothing else. 

Our Hero, Ignatius, simply adores imps. He is observing a line of imps, represented as a zero-indexed array of integers a of length n, where ai denotes the number of imps at the i-th position. Sometimes, imps can appear out of nowhere. When heroes fight imps, they select a segment of the line, start at one end of the segment, and finish on the other end, without ever exiting the segment. They can move exactly one cell left or right from their current position and when they do so, they defeat one imp on the cell that they moved to, so, the number of imps on that cell decreases by one. This also applies when heroes appear at one end of the segment, at the beginning of their walk. 

Their goal is to defeat all imps on the segment, without ever moving to an empty cell in it (without imps), since they would get bored. Since Ignatius loves imps, he doesn’t really want to fight them, so no imps are harmed during the events of this task. However, he would like you to tell him whether it would be possible for him to clear a certain segment of imps in the above mentioned way if he wanted to. 

You are given q queries, which have two types: 

  * 1 a b k — denotes that k imps appear at each cell from the interval [a, b]
  * 2 a b - asks whether Ignatius could defeat all imps on the interval [a, b] in the way described above 

Input

The first line contains a single integer n (1 ≤ n ≤ 200 000), the length of the array a. The following line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 5 000), the initial number of imps in each cell. The third line contains a single integer q (1 ≤ q ≤ 300 000), the number of queries. The remaining q lines contain one query each. Each query is provided by integers a, b and, possibly, k (0 ≤ a ≤ b < n, 0 ≤ k ≤ 5 000).

Output

For each second type of query output 1 if it is possible to clear the segment, and 0 if it is not.

Example

Input

3
2 2 2
3
2 0 2
1 1 1 1
2 0 2


Output

0
1

Note

For the first query, one can easily check that it is indeed impossible to get from the first to the last cell while clearing everything. After we add 1 to the second position, we can clear the segment, for example by moving in the following way: <image>.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, q;
struct tree {
  int siz;
  long long min0, min1, r, tag;
  void update(long long v) {
    if (siz & 1) r += v;
    tag += v;
    min0 += v;
  }
} t[1000010], ans;
tree operator+(const tree &x, const tree &y) {
  tree o;
  o.tag = 0;
  o.siz = x.siz + y.siz;
  if (y.siz & 1)
    o.r = y.r - x.r;
  else
    o.r = y.r + x.r;
  if (x.siz & 1) {
    o.min0 = min(x.min0, y.min1 + x.r);
    o.min1 = min(x.min1, y.min0 - x.r);
  } else {
    o.min0 = min(x.min0, y.min0 - x.r);
    o.min1 = min(x.min1, y.min1 + x.r);
  }
  return o;
}
void build(int rex, int l, int r) {
  if (l == r) {
    int x;
    scanf("%d", &x);
    t[rex] = (tree){1, x - 1, 1ll << 60, x - 1, 0};
    return;
  }
  int mid = (l + r) >> 1;
  build(rex + rex, l, mid);
  build(rex + rex + 1, mid + 1, r);
  t[rex] = t[rex + rex] + t[rex + rex + 1];
}
void pushdown(int rex) {
  if (t[rex].tag) {
    t[rex + rex].update(t[rex].tag);
    t[rex + rex + 1].update(t[rex].tag);
    t[rex].tag = 0;
  }
}
void ins(int rex, int l, int r, int x, int y, int v) {
  if (l == x && r == y) {
    t[rex].update(v);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(rex);
  if (y <= mid)
    ins(rex + rex, l, mid, x, y, v);
  else if (x > mid)
    ins(rex + rex + 1, mid + 1, r, x, y, v);
  else
    ins(rex + rex, l, mid, x, mid, v),
        ins(rex + rex + 1, mid + 1, r, mid + 1, y, v);
  t[rex] = t[rex + rex] + t[rex + rex + 1];
}
void query(int rex, int l, int r, int x, int y) {
  if (l == x && r == y) {
    ans = ans + t[rex];
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(rex);
  if (y <= mid)
    query(rex + rex, l, mid, x, y);
  else if (x > mid)
    query(rex + rex + 1, mid + 1, r, x, y);
  else
    query(rex + rex, l, mid, x, mid),
        query(rex + rex + 1, mid + 1, r, mid + 1, y);
}
int main() {
  scanf("%d", &n);
  build(1, 1, n);
  scanf("%d", &q);
  while (q--) {
    int cas, l, r, k;
    scanf("%d%d%d", &cas, &l, &r);
    l++, r++;
    if (cas == 1) {
      scanf("%d", &k);
      ins(1, 1, n, l, r, k);
    } else {
      ans = (tree){0, 1ll < 60, 1ll << 60, 0, 0};
      query(1, 1, n, l, r);
      puts(!ans.r && ans.min0 >= 0 && ans.min1 >= 0 ? "1" : "0");
    }
  }
  return 0;
}

```