Дано \(n\) діапазонів, ваше завдання полягає в тому, щоб визначити для кожного діапазону, чи містить він інший діапазон і чи містить його інший діапазон.

Діапазон \([a,b]\) містить діапазон \([c,d]\), якщо \(a≤c\) і \(d≤b\).

Обмеження

• \(1≤n≤2⋅10^5\)
• \(1≤x<y≤10^9\)

Формат вхідних даних

У першому рядку вхідних даних є ціле число \(n\): кількість діапазонів.

Після цього є \(n\) рядків, які описують діапазони. Кожен рядок містить два цілих числа \(x\) і \(y\): діапазон \([x,y]\). Ви можете припустити, що жоден діапазон не з’являється більше одного разу у вхідних даних.

Формат вихідних даних

Спочатку виведіть рядок, який описує для кожного діапазону (у порядку введення), чи містить він інший діапазон (1) чи ні (0). Потім надрукуйте рядок, який описує для кожного діапазону (у порядку введення), чи містить його інший діапазон (1) чи ні (0).

Приклад вхідних даних

4
1 6
2 4
4 8
3 6

Приклад вихідних даних

1 0 0 0
0 1 0 1