Varias encuestas indican que cuanto más alto eres, más alto puedes subir la escalera corporativa. En la corporación “TALL Enterprises Inc.” esta premisa es un hecho. La empresa lo ha formalizado de la siguiente manera: su jefe siempre es al menos tan alto como usted. Además, puede asumir con seguridad que su jefe gana un poco más que usted. De hecho, puede estar absolutamente seguro de que su jefe inmediato es la persona que gana el mínimo entre todos los empleados que ganan más que usted y son por lo menos tan altos como usted. Además, si usted es el jefe inmediato de alguien, esa persona es su subordinado, y todos sus subordinados son sus subordinados también. Si no eres el jefe de nadie, entonces no tienes subordinados.

Muchas personas que trabajan para TALL son inseguros de a quién deben enviar su informe de progreso semanal y cuántos subordinados tienen. Escriba un programa que le ayudará a determinar para cualquier empleado cuál es el jefe inmediato de ese empleado y cuántos subordinados tiene. La oficina de calidad en TALL ha ideado una serie de pruebas para asegurar que su programa es correcto. Estas pruebas se describen a continuación.

Entrada

En la primera línea de la entrada hay un solo entero positivo ~N~, indicando el número de casos de prueba a seguir. Cada escenario comienza con una línea que contiene dos enteros positivos ~M~ y ~Q~, donde ~M~ (como máximo ~30000~) es el número de empleados y ~Q~ (como máximo ~200~) es el número de consultas. Las siguientes ~M~ líneas describen cada empleado mediante tres números enteros: número de identificación del empleado (seis dígitos decimales, el primero de los cuales no es cero), salario anual en euros y finalmente altura en \(μm\) (\(1 μm\) ~=~ ~10^-6~ Metros - la precisión es importante en TALL). El presidente es el empleado que más gana y también es la persona más alta de la empresa. Luego siguen ~Q~ líneas que enumeran preguntas. Cada consulta es un ID de empleado legal único. El salario es un número entero positivo que es como máximo de ~10 000 000~. No hay dos empleados que tengan la misma identificación, y no hay dos empleados con el mismo salario. La altura de un empleado es de al menos \(1 000 000 μm\) y como máximo \(2 500 000 μm\).

Salida

Para cada consulta por empleado con ID ~X~ en la salida deberá imprimir una sola línea con dos enteros ~Y~ y ~K~, separados por un carácter de espacio, donde ~Y~ es el ID del jefe de ~X~, y ~K~ es el número de subordinados de ~X~. Si la consulta es la identificación del presidente, entonces para la salida en el ID de su jefe debe escribir ~0~ (ya que el presidente no tiene jefe inmediato excepto, posiblemente Dios).

Ejemplo de Entrada

2 
3 3 
123456 14323 1700000 
123458 41412 1900000 
123457 15221 1800000 
123456 
123458 
123457 
4 4 
200002 12234 1832001 
200003 15002 1745201 
200004 18745 1883410 
200001 24834 1921313 
200004 
200002 
200003 
200001

Ejemplo de Salida

123457 0 
0 2 
123458 1 
200001 2 
200004 0 
200004 0 
0 3