Heroes of Making Magic III

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 a _i 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 a ₁, a ₂, …, a _n (0 ≤ a _i ≤ 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: .

Solution:

#include <bits/stdc++.h>

using namespace std;

#define add_const ADD_CONST

struct Segment {
long long sum;
long long min_odd;
long long min_even;
int len;
};

Segment unite(Segment a, Segment b) {
Segment c;
c.len = b.len + a.len;
c.sum = b.sum + ((b.len & 1) ? (-a.sum) : a.sum);
if (a.len & 1) {
c.min_even = min(a.min_even, -a.sum + b.min_odd);
c.min_odd = min(a.min_odd, a.sum + b.min_even);
} else {
c.min_even = min(a.min_even, a.sum + b.min_even);
c.min_odd = min(a.min_odd, -a.sum + b.min_odd);
}
return c;
}

const int N = 1234567;

Segment a[N];
int add[N];

void build(int x, int l, int r) {
a[x].len = r - l + 1;
a[x].sum = a[x].min_odd = a[x].min_even = 0;
if (l < r) {
    int y = (l + r) >> 1;
build(x + x, l, y);
build(x + x + 1, y + 1, r);
}
}

void add_const(int x, int value) {
if (a[x].len & 1) {
a[x].sum += value;
}
a[x].min_odd += value;
add[x] += value;
}

void push(int x) {
if (add[x] != 0) {
add_const(x + x, add[x]);
add_const(x + x + 1, add[x]);
add[x] = 0;
}
}

void modify(int x, int l, int r, int ll, int rr, int v) {
if (ll <= l && r <= rr) {
    add_const(x, v);
    return;
  }
  push(x);
  int y = (l + r) >> 1;
if (ll <= y) {
    modify(x + x, l, y, ll, rr, v);
  }
  if (rr > y) {
modify(x + x + 1, y + 1, r, ll, rr, v);
}
a[x] = unite(a[x + x], a[x + x + 1]);
}

Segment solve(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
    return a[x];
  }
  push(x);
  int y = (l + r) >> 1;
Segment res;
if (rr <= y) {
    res = solve(x + x, l, y, ll, rr);
  } else {
    if (ll > y) {
res = solve(x + x + 1, y + 1, r, ll, rr);
} else {
res = unite(solve(x + x, l, y, ll, rr), solve(x + x + 1, y + 1, r, ll, rr));
}
}
a[x] = unite(a[x + x], a[x + x + 1]);
return res;
}

int main() {
int n;
scanf("%d", &n);
build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
    int foo;
    scanf("%d", &foo);
    modify(1, 0, n - 1, i, i, foo);
  }
  int tt;
  scanf("%d", &tt);
  while (tt--) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int from, to, value;
      scanf("%d %d %d", &from, &to, &value);
      modify(1, 0, n - 1, from, to, value);
    } else {
      int from, to;
      scanf("%d %d", &from, &to);
      Segment res = solve(1, 0, n - 1, from, to);
      printf("%d\n", (res.sum == (res.len & 1) && res.min_odd >= 1 && res.min_even >= 0) ? 1 : 0);
}
}
return 0;
}