University A will hold a programming contest this year as well. As a member of the writing team, you will be responsible for creating the input data for computational geometry problems. The input data you want to create is a set of line segments that are parallel to the x-axis or y-axis and do not touch each other. You develop a data generation program based on the following algorithm to generate input data.

1. Empty the set T of line segments on the xy plane.
2. Repeat the following process N times.
* Make a suitable line segment s parallel to the x-axis or y-axis.
* Add s to T if s does not touch any line segment in T, do not add s if it does.



Write a program that inputs N line segments parallel to the x-axis or y-axis in order and determines whether each line segment is added on the plane.



Input

The input is given in the following format.


N
px1 py1 qx1 qy1
px2 py2 qx2 qy2
::
pxN pyN qxN qyN


The number of line segments N (1 ≤ N ≤ 100000) is given in the first line. The following N lines are given the information of the line segment that you want to add to the i-th. The four integers pxi, pyi, qxi, qyi (0 ≤ pxi, pyi, qxi, qyi ≤ 109) given in each line are the x-coordinate, y-coordinate, and x of the other end point, respectively. Represents coordinates and y coordinates. However, the length of the line segment is 1 or more.

Output

For each line segment, "1" is output when added, and "0" is output on one line when not added.

Example

Input

9
0 2 5 2
1 3 1 7
0 6 3 6
2 4 8 4
4 0 4 5
6 3 6 0
5 6 7 6
8 3 8 7
6 5 11 5


Output

1
1
0
1
0
1
1
0
1
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree
{
  vector< set< int > > seg, lazy;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.resize(2 * sz - 1);
    lazy.resize(2 * sz - 1);
  }

  bool query(int a, int b, int low, int high, int k, int l, int r)
  {
    if(a >= r || b <= l) return (true);
    if(lazy[k].lower_bound(low) != lazy[k].lower_bound(high)) return (false);
    if(a <= l && r <= b) return (seg[k].lower_bound(low) == seg[k].lower_bound(high));
    return (query(a, b, low, high, 2 * k + 1, l, (l + r) >> 1) &&
            query(a, b, low, high, 2 * k + 2, (l + r) >> 1, r));
  }

  void add(int a, int b, int x, int k, int l, int r)
  {
    if(a >= r || b <= l) {
      return;
    } else if(a <= l && r <= b) {
      lazy[k].insert(x);
    } else {
      add(a, b, x, 2 * k + 1, l, (l + r) >> 1);
      add(a, b, x, 2 * k + 2, (l + r) >> 1, r);
      seg[k].insert(x);
    }
  }

  bool query(int a, int b, int low, int high)
  {
    return (query(a, b, low, high, 0, 0, sz));
  }

  void add(int a, int b, int x)
  {
    add(a, b, x, 0, 0, sz);
  }
};

int main()
{
  int N, px[100000], py[100000], qx[100000], qy[100000];
  vector< int > x, y;

  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d %d %d %d", px + i, py + i, qx + i, qy + i);
    if(px[i] > qx[i]) swap(px[i], qx[i]);
    if(py[i] > qy[i]) swap(py[i], qy[i]);
    x.push_back(px[i]);
    x.push_back(qx[i]);
    y.push_back(py[i]);
    y.push_back(qy[i]);
  }

  sort(begin(x), end(x));
  x.erase(unique(begin(x), end(x)), end(x));
  sort(begin(y), end(y));
  y.erase(unique(begin(y), end(y)), end(y));

  SegmentTree xx(x.size()), yy(y.size());
  for(int i = 0; i < N; i++) {
    px[i] = lower_bound(begin(x), end(x), px[i]) - begin(x);
    py[i] = lower_bound(begin(y), end(y), py[i]) - begin(y);
    qx[i] = lower_bound(begin(x), end(x), qx[i]) - begin(x);
    qy[i] = lower_bound(begin(y), end(y), qy[i]) - begin(y);

    if(xx.query(px[i], qx[i] + 1, py[i], qy[i] + 1) &&
       yy.query(py[i], qy[i] + 1, px[i], qx[i] + 1)) {
      puts("1");
      if(px[i] == qx[i]) yy.add(py[i], qy[i] + 1, px[i]);
      else xx.add(px[i], qx[i] + 1, py[i]);
    } else {
      puts("0");
    }
  }

}