If it was so, then let's make it a deal...
К сожалению, даже после десяти лет копирования картин известных художников, Эрик все еще не смог стать искусным художником-импрессионистом. Он хочет что-то забыть, но феномен белого медведя продолжает нависать над ним.
Эрик до сих пор помнит \(n\) впечатлений в виде целочисленного массива. Он записал их как \(w_1, w_2, \ldots, w_n\). Однако у него плохая память на впечатления. Для каждого \(1 \leq i \leq n\) он только запомнил, что выполнялось условие \(l_i \leq w_i \leq r_i\).
Эрик считает, что впечатление \(i\) является уникальным тогда и только тогда, когда существует массив \(w_1, w_2, \ldots, w_n\), в котором \(w_i \neq w_j\) выполняется для всех \(1 \leq j \leq n\), где \(j \neq i\).
Пожалуйста, помогите Эрику определить, является ли впечатление \(i\) уникальным для каждого \(1 \leq i \leq n\), независимо для каждого \(i\). Возможно, ваше суждение поможет переписать финальную историю.
Выходные данные
Для каждого набора входных данных выведите бинарную строку \(s\) длины \(n\): для каждого \(1 \leq i \leq n\), если впечатление \(i\) уникально, то \(s_i=\texttt{1}\); в противном случае, \(s_i=\texttt{0}\). Выводите строку без пробелов.
Примечание
В первом наборе входных данных единственным возможным массивом \(w\) является \([1, 1]\), в котором ни \(1\), ни \(2\) впечатления не являются уникальными (поскольку \(w_1 = w_2\)).
Во втором наборе входных данных все впечатления могут быть уникальными:
- Для \(i = 1\) мы можем сделать \(w\) равным \([1, 3, 2, 3]\), и в нём \(w_1 \neq w_2\), \(w_1 \neq w_3\) и \(w_1 \neq w_4\);
- Для \(i = 2\) мы можем сделать \(w\) равным \([2, 3, 1, 2]\), и в нём \(w_2 \neq w_1\), \(w_2 \neq w_3\) и \(w_2 \neq w_4\);
- Для \(i = 3\) мы можем сделать \(w\) равным \([1, 1, 3, 1]\);
- Для \(i = 4\) мы можем сделать \(w\) равным \([2, 3, 3, 1]\).
В третьем наборе входных данных, для \(i = 4\) мы можем сделать \(w\) равным \([3, 2, 2, 1, 3, 2]\). Таким образом, впечатление \(4\) — уникально.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
1 1
1 1
4
1 3
1 3
1 3
1 3
6
3 6
2 2
1 2
1 1
3 4
2 2
7
3 4
4 4
4 4
1 3
2 5
1 4
2 2
3
4 5
4 4
5 5
|
00
1111
100110
1001111
011
|