题目内容

档案室夜班要把当天的调档请求排进一排查阅窗。值班员必须先给自己留出一个空窗去核总账，再判断剩下的窗够不够分给所有调档员，并把每个窗能不能留空写进值班日志。

今晚共有 $k$ 名调档员，查阅窗编号为 $1,2,\dots,k+1$，一共 $k+1$ 个窗。第 $i$ 名调档员只接受闭区间 $[p_i,q_i]$ 里的整数编号窗。每名调档员必须恰好分到一个窗，同一个窗最多分给一名调档员。

对每个窗 $t$，请独立判断：如果窗 $t$ 完全不分配、专门留给值班员，是否仍然能把全部 $k$ 名调档员安排到各自能接受、且互不冲突的窗上。

请按窗号从小到大输出判断结果。判断不同的 $t$ 时，可以采用完全不同的分配方案。

调档员人数满足 $1 \le k \le 2 \times 10^5$，且 $1 \le p_i \le q_i \le k+1$。

输入描述

第一行一个整数 $k$（$1 \le k \le 2 \times 10^5$），表示调档员人数。

接下来 $k$ 行，第 $i$ 行两个整数 $p_i$、$q_i$（$1 \le p_i \le q_i \le k+1$），表示第 $i$ 名调档员能接受的窗号闭区间。

输出描述

输出一个长度为 $k+1$ 的 01 字符串。第 $t$ 个字符为 1，当且仅当存在一种合法安排，使全部调档员都分到窗、且窗 $t$ 不分配给任何人；否则为 0。

样例1

输入

1
1 2

输出

11

说明

只有一名调档员，两个窗都能接受。留空窗 1 时分到 2，留空窗 2 时分到 1，两种都可行。

样例2

输入

3
1 4
2 2
3 3

输出

1001

说明

• 留空窗 1：三人可分别分到 4、2、3。
• 留空窗 2：第二人只接受窗 2，无法安排。
• 留空窗 3：第三人只接受窗 3，无法安排。
• 留空窗 4：三人可分别分到 1、2、3。

样例3

输入

3
1 2
1 2
2 2

输出

0000

说明

三人都只能挤在窗 1、2 里，这两个窗本身就装不下三个人。无论留空哪一个窗，都无法安排，因此四个位置都是 0。