/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1000006;
#define X first.first
#define Y first.second
#define I second
#define pt pair<pair<int,int>, int>
int n, k;
int ans[N];
pt p[N];
vector<pt> y[N];
int used_x[N];
vector<int> last_x[N];
int ly[N], ry[N];
void lesgo(int i, pt a)
{
int pos;
if (used_x[a.X] > 2)
{
used_x[a.X]--;
int last_y = last_x[a.X].back();
if (y[last_y][ly[last_y]].X == y[last_y][ry[last_y]].X)
{
last_x[y[last_y][ly[last_y]].X].pop_back();
ly[last_y]++;
}
else if (y[last_y][ly[last_y]].X == a.X)
{
pos = ly[last_y];
last_x[y[last_y][pos].X].pop_back();
pos++;
ly[last_y] = pos;
if (pos < ry[last_y])
{
used_x[y[last_y][pos].X]++;
lesgo(last_y, y[last_y][pos]);
last_x[y[last_y][pos].X].push_back(last_y);
}
}
else
{
pos = ry[last_y];
last_x[y[last_y][pos].X].pop_back();
pos--;
ry[last_y] = pos;
if (pos > ly[last_y])
{
used_x[y[last_y][pos].X]++;
lesgo(last_y, y[last_y][pos]);
last_x[y[last_y][pos].X].push_back(last_y);
}
}
}
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i].X >> p[i].Y;
k = max(k, max(p[i].X, p[i].Y));
p[i].I = i;
y[p[i].Y].PB(p[i]);
}
for (int i = 1; i <= k; i++)
sort(all(y[i]));
for (int i = 1; i <= k; i++)
{
if(y[i].empty())
continue;
used_x[y[i][0].X]++;
ly[i] = 0;
lesgo(i, y[i][0]);
last_x[y[i][0].X].push_back(i);
ry[i] = y[i].size() - 1;
if (ly[i] != ry[i])
{
used_x[y[i].back().X]++;
lesgo(i, y[i].back());
last_x[y[i].back().X].push_back(i);
}
}
for (int i = 1; i <= k; i++)
{
if(y[i].empty())
continue;
if(ly[i] <= ry[i])
ans[y[i][ly[i]].I] = ans[y[i][ry[i]].I] = 1;
}
int l, r;
for (int i = 1; i <= k; i++)
{
l = 0;
r = x[i].size() - 1;
while (l < x[i].size() && !ans[x[i][l].I])
l++;
while (r >= 0 && !ans[x[i][r].I])
r--;
if (l + 1 <= r - 1)
assert(0);
l = 0;
r = y[i].size() - 1;
while (l < y[i].size() && !ans[y[i][l].I])
l++;
while (r >= 0 && !ans[y[i][r].I])
r--;
if (l + 1 <= r - 1)
assert(0);
}
for (int i = 1; i <= n; i++)
cout << ans[i];
cout << endl;
}
int main()
{
fastIO;
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
/*
8
1 1
2 1
3 1
1 2
2 2
3 2
2 3
3 3
9
1 1
1 2
2 2
1 3
1 4
1 5
2 5
1 6
1 7
20
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4
1 5
2 5
3 5
4 5
16
1 1
2 1
3 1
4 1
1 2
2 2
4 2
1 3
2 3
3 3
4 3
1 4
4 4
1 5
2 5
3 5
*/
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:137:13: error: 'x' was not declared in this scope
137 | r = x[i].size() - 1;
| ^
Main.cpp:151:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | while (l < y[i].size() && !ans[y[i][l].I])
| ~~^~~~~~~~~~~~~
