Dados ~n~ rangos, su tarea consiste en determinar para cada rango si contiene algún otro rango y si algún otro rango lo contiene. El rango ~[a,b]~ contiene al rango ~[c,d]~ si ~a \leq c~ y ~d \leq b~.

Entrada

La primera línea de entrada tiene un número entero ~n~: el número de rangos. Después, hay ~n~ líneas que describen los rangos. Cada línea tiene dos enteros ~x~ e ~y~: el rango es ~[x,y]~. Puede suponer que ningún rango aparece más de una vez en la entrada.

Salida

Primero imprima una línea que describa para cada rango (en el orden de entrada) si contiene algún otro rango (1) o no (0). A continuación, imprima una línea que describa para cada rango (en el orden de entrada) si algún otro rango lo contiene (1) o no (0).

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~
• ~1 \leq x < y \leq 10^9~

Ejemplo de Entrada

4
1 6
2 4
4 8
3 6

Ejemplo de Salida

1 0 0 0
0 1 0 1