Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

En una fábrica de dulces, hay una máquina misteriosa. La máquina produce dulces deliciosos, cada uno un poco diferente de los demás. La máquina tiene una línea de ranuras de salida, numeradas del $1$ al $n$, de las cuales los caramelos se caen tan pronto como están listos. Nadie sabe realmente cómo funciona la máquina, pero antes de que comience una sesión de producción, imprime una lista que le dice al dueño de la fábrica, cuándo y de qué ranura se desprenderá cada dulce.

Ahora, el propietario de la fábrica puede instalar vagones automáticos que se mueven por debajo de las ranuras de salida para atrapar los caramelos que caen. Por supuesto, ninguno de los dulces debería caer al suelo y echarse a perder. Sin embargo, como el funcionamiento de los vagones es costoso, el propietario desea instalar el menor número de vagones posible. Escriba un programa que calcule el número mínimo de vagones necesarios para atrapar todos los dulces. Además, su programa debe mostrar qué vagón debe atrapar qué dulce. Los vagones funcionan a una velocidad de un ancho de ranura por segundo. Antes de que comience el proceso de producción, cada vagón se puede mover a la ranura donde debe atrapar su primer caramelo.

Input

La entrada se lee desde la entrada estándar y describe una sesión de producción de la máquina. La primera línea contiene exactamente un número entero $n$ $(1 \leq n \leq 10^5)$, la cantidad de caramelos producidos en esa sesión. Cada una de las siguientes $n$ líneas contiene un par de enteros $s_i$ y $t_i$ $(0 \leq s_i, t_i \leq 10^9)$, ranura de salida y tiempo para el caramelo $i$. Cada par $(s_i, t_i)$ es único.

Output

La salida debe escribirse hacia la salida estándar. La primera línea del resultado contiene exactamente un número entero $w$, el número mínimo de vagones necesarios para atrapar todos los dulces. Los vagones están numerados de $1$ a $w$. Las siguientes $n$ líneas indican qué vagón atrapará qué dulce. Para ese propósito, cada una de estas líneas contiene tres enteros: ranura de salida $s_j$ y tiempo de salida $t_j$ para algún caramelo $j$ y un número de vagón $w(j)$, de modo que en el tiempo $t_j$ el vagón $w(j)$ estará en la ranura $s_j$ y por lo tanto será capaz de atrapar el caramelo $j$.

Dado que se deben capturar todos los dulces, cada par de ranura y tiempo deben aparecer en exactamente una línea de salida (en cualquier oden). Si existe más de una solución, imprima una de ellas.

Sample test(s)