Cumpleaños en el jardín de infancia
Las dinámicas que se crean en las aulas de las escuelas infantiles alrededor de los cumpleaños de los críos son una locura. Para que no haya envidias ni se creen conflictos entre ellos, todos los niños celebran su cumpleaños e invitan a todos los demás de la clase. Eso supone un caos de regalos que crece de forma exponencial con su tamaño.
Para poner fin a esta locura, Justo Reparto, el padre de una de las niñas que asiste al jardín de infancia "Acepto el retoño" ha tenido una idea para el curso que viene. En lugar de tanta celebración, ha propuesto hacer solo una, aunque sea a lo grande, en la que todo el mundo se dé por celebrado, felicitado y regalado. Para eso, cada niño aportará a la celebración un regalo. Luego los regalos se repartirán entre todos, de modo que a cada peque le toque uno, sea el que sea. De esa forma también aprenderán que no hay juguetes de niño y juguetes de niña, porque podría ocurrir que su hija terminara llevándose un camión de bomberos, y el pequeño Mambrú Tote una muñeca.
Aceptada la idea, se ha decidido que para repartir los regalos entre los niños, se usará un amidakuji (o Ghost leg), un juego japonés de reparto de n objetos entre n personas. Se comienza con una hoja de papel en la que se escriben en la parte superior los nombres de las personas, y, alineados en la parte inferior, los objetos, conectando con una línea vertical un objeto con una persona. A continuación se incorporan, de forma arbitraria, líneas horizontales para conectar dos líneas verticales adyacentes, garantizando, eso sí, que no haya líneas horizontales que se toquen.
Para saber qué regalo le toca a cada uno, se siguen las líneas de arriba hacia abajo sabiendo que cada vez que se alcanza una línea horizontal hay que seguirla para cambiar de columna de descenso.
Para evitar que se haga trampa, Justo Reparto pondrá las líneas verticales, los nombres y los regalos en el orden que le parezca, y los tapará. Luego los niños pondrán las líneas horizontales sin saber qué están uniendo. Justo tiene la idea, aunque no lo haya dicho, de colococar en la misma columna a cada niño y el regalo que ha traído, de modo que, si no se ponen líneas horizontales, todos se vayan a casa con su propio regalo. Además, colocará los regalos ordenados por su valor empezando, a la izquierda, con el más barato.
Entrada
La entrada comienza con un número que indica cuántos casos de prueba tendrán que procesarse. Cada uno comienza con un número 2 ≤ N ≤ 200.000 indicando cuántos niños asisten al cumpleaños, cada uno con un regalo.
Después aparecen N−1 líneas, una por cada columna del amidakuji, de izquierda a derecha, salvo para la última. Cada una comienza con el número de líneas horizontales que salen de esa columna hacia la siguiente a su derecha. A continuación aparece un número por cada conexión, indicando la distancia a la que está de la parte superior de la figura.
En ningún caso hay más de 200.000 líneas horizontales, y ninguna está a una distancia mayor de 109 del inicio de las columnas. Todas las conexiones son completamente horizontales y se garantiza que no existirá ninguna columna con dos o más conexiones a la misma altura (hacia la izquierda o hacia la derecha).
Salida
Por cada caso de prueba se escribirá una línea con tres números separados por espacio. El primero indica cuántos niños obtienen un regalo peor que el que aportaron (queda a la izquierda de su posición), el segundo indica cuántos se llevan el regalo que llevaron a la celebración, y el tercero cuántos se llevan un regalo mejor que el que entregaron (queda a la derecha).
Entrada de ejemplo
3 4 1 1 2 2 3 3 5 1 4 2 1 1 4 1 1 1 2 0
Salida de ejemplo
2 0 2 1 0 1 2 1 1