#include <bits/stdc++.h> using namespace std; int mil = 1000003; struct pnt { int x,y,i; }; bool compX(pnt a, pnt b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } bool compY(pnt a, pnt b) { if (a.y != b.y) return a.y < b.y; return a.x < b.x; } void rem(int x, vector<int>& Le, vector<int>& Ri, vector<int>& Up, vector<int>& Do) { int l = Le[x], r = Ri[x]; if (l != -1) Ri[l] = r; if (r != -1) Le[r] = l; int u = Up[x], d = Do[x]; if (u != -1) Do[u] = d; if (d != -1) Up[d] = u; return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,i; cin >> n; vector<pnt> XY(n); vector<int> L(mil, mil), R(mil, -1), U(mil, -1), D(mil, mil); vector<int> Le(n, -1), Ri(n, -1), Up(n, -1), Do(n, -1); vector<int> X(n), Y(n); i = -1; while (++i < n) { cin >> XY[i].x >> XY[i].y; XY[i].i = i; XY[i].x--; XY[i].y--; X[i] = XY[i].x; Y[i] = XY[i].y; } sort(XY.begin(), XY.end(), compX); i = 0; while (++i < n) { int idxPrev = XY[i-1].i, idx = XY[i].i; if (XY[i-1].x == XY[i].x) Do[idx] = idxPrev; } i = n-1; while (i--) { int idxPrev = XY[i+1].i, idx = XY[i].i; if (XY[i].x == XY[i+1].x) Up[idx] = idxPrev; } sort(XY.begin(), XY.end(), compY); i = 0; while (++i < n) { int idxPrev = XY[i-1].i, idx = XY[i].i; if (XY[i-1].y == XY[i].y) Le[idx] = idxPrev; } i = n-1; while (i--) { int idxPrev = XY[i+1].i, idx = XY[i].i; if (XY[i].y == XY[i+1].y) Ri[idx] = idxPrev; } vector<bool> srchd(n, false); vector<int> Ac(n, 0); /*for (auto x: Le) cout << x << "l "; cout << "\n"; for (auto x: Ri) cout << x << "r "; cout << "\n"; for (auto x: Up) cout << x << "u "; cout << "\n"; for (auto x: Do) cout << x << "d "; cout << "\n";*/ queue<int> BFS; i = -1; while (++i < n) { if (((Le[i] == -1) || (Ri[i] == -1)) && ((Up[i] == -1) || (Do[i] == -1))) { //cout << i << "yo\n"; BFS.push(i); } } vector<int> eel, eeled(n, 0); int sleft = n; while (sleft > 0) { //cout << sleft << "\n"; while (BFS.size()) { int u = BFS.front(); BFS.pop(); if (u == -1) continue; if (srchd[u]) continue; int x = X[u], y = Y[u]; int ll = Le[u], rr = Ri[u], uu = Up[u], dd = Do[u]; //cout << u << " " << ll << " " << rr << " " << uu << " " << dd << "\n"; if ((ll == -1) || (rr == -1) || (uu == -1) || (dd == -1)) { if (!eeled[u]) { eel.push_back(u); eeled[u] = true; } } if (((L[y] < x) && (x < R[y])) || ((D[x] < y) && (y < U[x]))) { //reduce //cout << L[y] << " " << R[y] << " " << D[x] << " " << U[x] << "quad\n"; srchd[u] = true; rem(u, Le, Ri, Up, Do); } else if (((ll == -1) || (rr == -1)) && ((uu == -1) || (dd == -1))) { //free //cout << u << "inside\n"; srchd[u] = true; Ac[u] = 1; L[y] = min(L[y], x); R[y] = max(R[y], x); D[x] = min(D[x], y); U[x] = max(U[x], y); } if (srchd[u]) { sleft--; BFS.push(ll); BFS.push(rr); BFS.push(uu); BFS.push(dd); } } if (sleft == 0) break; while (eel.size()) { i = *eel.rbegin(); eel.pop_back(); if (srchd[i]) continue; int ll = Le[i], rr = Ri[i], uu = Up[i], dd = Do[i]; int x = X[i], y = Y[i]; if ((ll == -1) || (rr == -1) || (uu == -1) || (dd == -1)) { Ac[i] = 1; srchd[i] = true; L[y] = min(L[y], x); R[y] = max(R[y], x); D[x] = min(D[x], y); U[x] = max(U[x], y); sleft--; BFS.push(ll); BFS.push(rr); BFS.push(uu); BFS.push(dd); break; } } } vector<char> ok(n); i = -1; while (++i < n) { if (Ac[i]) ok[i] = '1'; else ok[i] = '0'; } string ta(ok.begin(), ok.end()); cout << ta << "\n"; }