Problema número 712

Eventos de los partidos

Tiempo máximo: 1,000-4,000 sMemoria máxima: 16384 KiB
Gráfico de barras esquemático sobre un campo de fútbol

Para conseguir retransmisiones vibrantes e información estadística sobre los enfrentamientos de un torneo de fútbol, durante los partidos se anotan multitud de eventos sobre los sucesos que ocurren en el encuentro. Para cada uno, se guarda el instante exacto en el que ocurrió junto con una descripción. Por ejemplo, en la final de la Copa Mundial Femenina de Fútbol de 2023 se anotaron eventos sobre faltas, saques de esquina, amonestaciones, cambios de jugadoras y, como no, el del gol que llevó a España a la victoria.

Al final del partido se termina con un conjunto ordenado enorme de eventos. Cuando se hacen los resúmenes de los partidos, es interesante encontrar rápidamente los momentos más intensos del enfrentamiento, es decir aquellos periodos con un mayor número de eventos.

Entrada

Cada caso de prueba comienza con un número 1 ≤ N ≤ 400.000 que indica cuántos eventos se han anotado durante un partido de fútbol. A continuación aparecen N líneas, cada una describiendo un evento con un número indicando el instante en el que se ha producido y una descripción de como mucho 80 letras y espacios. Los eventos están ordenados cronológicamente. El tiempo se mide desde el inicio del partido en unas unidades extrañas que proporcionan mucha precisión, por lo que los números tienen valores entre 0 y 1.000.000.000. Aun así, puede ocurrir que dos eventos ocurran exactamente en el mismo instante. Por ejemplo, cuando se produce un cambio de jugadoras del campo, aparece un evento que indica que una jugadora sale y otro que indica que una jugadora entra, y se registran con el mismo tiempo.

Tras los eventos viene un número 1 ≤ Q ≤ 1.000 indicando cuántas consultas se realizan sobre los datos. A continuación aparecen Q líneas, cada una con una consulta formada por un número 1 ≤ q ≤ N. Se garantiza que N×Q ≤ 5.000.000.

Salida

Por cada consulta q se buscará el periodo más corto del partido en el que hayan ocurrido al menos q eventos. Si hay varios de la misma longitud temporal se preferirá aquél que incluya más eventos. Si hay varias posibilidades se preferirá el que ocurra antes.

Por cada consulta se escribirá el instante de tiempo en el que empieza el periodo encontrado, el instante en el que termina y el número de eventos que incluye. Tras la respuesta a las consultas de cada caso de prueba se escribirá una línea con tres guiones (---).

Entrada de ejemplo

10
300 Fuera de juego de Russo
1749 Gol de Olga Carmona
2241 Disparo a puerta de Alba Redondo
2791 Sale Alessia Ruso
2791 Entra Lauren James
3076 Saque de esquina
3333 Tarjeta amarilla para Lauren Hemp
5433 Sale Mariona Caldentey
5433 Entra Alexia Putellas
6327 Fin del partido
3
1
5
7

Salida de ejemplo

2791 2791 2
2241 3333 5
300 3333 7
---