¿Tulancingo de Bravo es más grande que Pachuca de Soto?

Descripción

En tu pueblito natal hay una carretera que se puede representar como una línea recta con los puntos \(0, 1, 2, 3, ... , \infty\) (es una carretera muy larga). Por esta ruta pasa un camión que empieza desde el punto \(0\) (y sin pasajeros) y avanzará a cada punto consecutivamente; este camión puede detenerse para subir o bajar personas en cada punto de la recta. Como Tulancingo es algo extraño, no es raro que el chofer sea siempre el mismo y este tenga unas reglas particulares que todos los pasajeros siguen para subirse al camión y saber dónde sentarse. Como el chofer quiere saber en dónde se sentará cada persona (nunca se sabe cuándo le será útil esa información), le ha pedido a los checadores, que hay en cada parada, que le manden una lista con el destino de cada persona que esté esperando a que pase el camión.

El camión en esencia cosiste en \(n\) filas con \(4\) columnas cada una. Y sigue la estructura básica de un autobús de pasajeros ordinario:

• La columna \(1\) y \(2\) representan los asientos del lado izquierdo, mientras que las columnas \(3\) y \(4\) los del lado derecho (en medio de estas columnas existe un pasillo en donde transitan los pasajeros).
• En la columna \(1\) está la ventana del lado izquierdo, mientras que la ventana del lado derecho está en la columna \(4\).

Una vez explicado esto, ahora las reglas que tiene el chofer son las siguientes:

• Si hay personas que van a bajar y subir en un mismo punto de la recta, se dejará bajar primero a todos los pasajeros y después entrarán los nuevos pasajeros.
• Si hay varías personas que se subirán en el mismo punto, los criterios para saber cómo se irán subiendo son los siguientes:
  • Se acomodarán de tal forma que esté primero la persona que más pronto se vaya a bajar, despúes la segunda persona más próxima a bajar y así sucesivamente.
  • En caso de que haya empates (hay personas que se bajan en el mismo lugar), estos se acomodarán en el orden que está en la lista que los checadores le mandaron al chofer (el que aparezca primero en esa lista).
• Cada persona que entre buscará un asiento disponible en la fila \(1\), si no hay buscará en la fila \(2\), si tampoco hay pasará a la fila \(3\) y así sucesivamente.
• Si no hay ningún asiento disponible (el camión va lleno) la persona no se subirá (el chofer es consciente que traer personas paradas en un riesgo).
• En la primera fila que haya un asiento disponible, la persona se sentará respecto a la siguiente prioridad:
  1. El asiento con la ventana izquierda (columna \(1\)).
  2. El asiento con la ventana derecha (columna \(4\)).
  3. El asiento a un lado de la ventana izquierda (columna \(2\)).
  4. El asiento a un lado de la ventana derecha (columna \(3\)).
• Si una persona que estaba en un asiento con ventana se baja y hay una persona a su lado que todavía no se baja en ese punto, este pasajero se pasará a la ventana (porque a todos les gusta estar de ese lado).

Se recomienda ver los ejemplos para entender mejor todo.

Problema

Como el chofer no es muy bueno haciendo cálculos, te ha pedido tu ayuda para que, dada la lista que le entregaron los checadores con los puntos en donde se subirán y bajarán las personas, le digas la posición en dónde se sentará cada persona al momento de subirse al camión.

Entrada

• En la primera línea habrá dos números \(x\) y \(n\). La cantidad de personas que hay en lista de los checadores y la cantidad de filas que tiene el camión, respectivamente.
• En las siguientes \(x\) líneas habrá dos números \(l\) y \(r\). El punto de subida y de bajada de cada pasajero, respectivamente.

Salida

Para cada pasajero en la lista, se deberá imprimir las coordenadas del asiento en donde se sentará. En caso de que no se pueda subir la persona (porque el camión va lleno), se deberá imprimir un -1.

Ejemplos

Entrada

3 5
3 10
1 3
1 2

Salida

1 1
1 4
1 1

Explicación:

• El camión tiene \(5\) filas, empieza en el punto \(0\) y está vacío, al llegar al punto \(1\) hay dos pasajeros esperando y pasa lo siguiente:
  • El primer pasajero en subir es el que aparece en el índice \(3\) de la lista, ya que es el que primero se baja, por lo tanto para la tercera persona en la lista, su asiento será la fila \(1\) y columna \(1\).
  • El segundo pasajero en subir es el que aparece en el índice \(2\) de la lista. Como la ventana del lado izquierdo está ocupada, se sentará en la ventana derecha en la fila \(1\) y columna \(4\).
• Cuando el camión avance y llegue al punto \(2\), la persona que estaba en la fila \(1\) y columna \(1\) se bajará.
• Cuando el camión avance y llegue al punto \(3\), primero se bajará la persona que aparece en el índice \(2\) de la lista. Después de eso, se subirá la persona que está en el índice \(1\) de la lista y este se sentará en la fila \(1\) columna \(1\).

Entrada

5 2
1 3
1 10
1 2
1 5
1 20

Salida

1 4
1 3
1 1
1 2
2 1

Explicación:

• El camión tiene \(2\) filas, empieza en el punto \(0\) y está vacío, al llegar al punto \(1\) hay 5 pasajeros esperando y pasa lo siguiente:
  • El primero en subirse es el pasajero que se baja en el punto \(2\) (índice \(3\) en la lista), por lo tanto a él le toca el asiento de la ventana izquierda (posición \(1\) y \(1\)).
  • El segundo en subirse es el pasajero que se baja en el punto \(3\) (índice \(1\) en la lista), por lo que se sentará en la ventana derecha (posición \(1\) y \(4\)).
  • El tercero en subirse es el pasajero que se baja en el punto \(5\) (índice \(4\) en la lista), por lo que se sentará a un lado del asiento de la ventana izquierda (posición \(1\) y \(2\)).
  • El cuarto en subirse es el pasajero que se baja en el punto \(10\) (índice \(2\) en la lista), por lo que se sentará a un lado del asiento de la ventana derecha (posición \(1\) y \(3\)).
  • El quinto pasajero en subirse es el que se baja en el punto \(20\) (índice \(5\) en la lista), toda la primera fila está ocupada, por lo que se pasará a la segunda fila la cual está vacía y se sentará en la ventana izquierda.

Entrada

5 1
1 5
1 4
1 5
1 5
1 5

Salida

1 4
1 1
1 2
1 3
-1

Límites

• \(1 \leq x \leq 1000\).
• \(1 \leq n \leq 100\).
• \(1 \leq l \lt r \leq 100\).