3868 - Professor Bill

Created by Frank Arteaga Salgado, Carlos Joa
Added by frankr (2017-06-28)
Limits
Total Time: 15000 MS | Test Time: 2000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Professor Bill organizes many activities to promote the ACM-ICPC. In his talks, one of the most effective ways to explain several aspects of a programming contest is to show a live scoreboard of a contest. Thanks to some wonderful applications that are able to reproduce a live ranking of a previous contest, he does not need an active contest to do a demo.  Furthermore, some of the applications allow him to increase the contest simulation speed so that the demo takes only a fraction of the time the real contest lasted.

Nevertheless, for his next talk, Bill decides that it is best to show the shortest time interval in which all teams has at least one submission. Since the app he uses for the demo lacks the functionality to find this shortest interval, Bill has assigned you the task to find such an interval given the contest submission data feed in the exact format that the app receives it.
El profesor Bill realiza muchas acciones para dar a conocer el ACM-ICPC. En sus charlas una de las formas más efectivas de explicar varias cuestiones de la competencia es mostrando el ranking vivo de alguna competencia. Gracias a las aplicaciones que reproducen el ranking de una competencia previa, él no necesita de una competencia en vivo para hacerlo, además, él puede acelerar algo el tiempo en la app de modo que el ejemplo no dure varias horas.

Sin embargo, para su próxima charla, Bill decide que es mejor escoger el menor intervalo de tiempo en que todos los equipos hicieron al menos un envío para ser juzgado; entonces, ese intervalo es el que configura en la app para su charla. La app escogida carece de esta funcionalidad para encontrar tal intervalo, por lo que tu tarea es programar un algoritmo que lo encuentre dados los datos de la competencia en el formato específico que los recibe la app.

;jsessionid=D9FD23B8F94BACCD151C9861E03D854F
Professor Bill organizes many activities to promote the ACM-ICPC. In his talks, one of the most effective ways to explain several aspects of a programming contest is to show a live scoreboard of a contest. Thanks to some wonderful applications that are able to reproduce a live ranking of a previous contest, he does not need an active contest to do a demo.  Furthermore, some of the applications allow him to increase the contest simulation speed so that the demo takes only a fraction of the time the real contest lasted.

Nevertheless, for his next talk, Bill decides that it is best to show the shortest time interval in which all teams has at least one submission. Since the app he uses for the demo lacks the functionality to find this shortest interval, Bill has assigned you the task to find such an interval given the contest submission data feed in the exact format that the app receives it.

Input specification

On the first line, there is an integer K (1 ≤ K ≤ 105), the number of teams in the contest.

The following K lines describe the contest submission data feed consisting of all submission times from each team. The i-th line contains the submission times from the i-th team.

C1 T11 T12 ... T1C1
.
.
CK TK1 TK1 ... TKCK

Where:
  • C1, C2, ..., CK (0 ≤ C1 + C2 + ... + CK ≤ 2*105) are the number of submissions sent by teams 1 to respectively.
  • Tij, (0 < Tij ≤ 109), for valid indices i and j, are the submission times from team i. Time is measure in milliseconds from the start of the contest. For each team, times are sorted in increasing order.
You may be wondering where are the team names and the verdicts of the submissions. Well, the app receives them from another data feed. To solve the current task, you do not need them, or do you? In addition, the submission times may seem excessive, but they are actually from a progressive contest that lasts for several days ;)
En la primera línea aparecerá un entero K (1 ≤ K ≤ 105) que representa la cantidad de equipos de la competencia.

En las siguientes K líneas estarán los datos de todos los envíos de los equipos. En la i-ésima línea se encuentran los datos del i-ésimo equipo.

C1 T11 T12 ... T1C1
.
.
CK TK1 TK1 ... TKCK

Donde:
  • C1, C2, ..., CK son las cantidades de envíos de los equipos 1 al (0 ≤ C1 + C2 + ... + CK ≤ 2*105)
  • Tij, (0 < Tij ≤ 109), para valores válidos de i y j, serían los tiempos en que se realiza cada envío. Los tiempos se miden en milisegundos desde el inicio de la competencia. Los tiempos de cada equipo están ordenados.
Usted se preguntaría ¿dónde están los nombres de los equipos y los resultados de los envíos;jsessionid=D9FD23B8F94BACCD151C9861E03D854F? Bueno, los mismos la app los toma de otro fichero con formato similar al descrito. Pero para resolver este problema usted no los necesita, ¿o sí? Además, puede parecerle exagerada la duración de la competencia, no se asombre, pues los datos son de progresivos de varios días ;)
On the first line, there is an integer K (1 ≤ K ≤ 105), the number of teams in the contest.

The following K lines describe the contest submission data feed consisting of all submission times from each team. The i-th line contains the submission times from the i-th team.

C1 T11 T12 ... T1C1
.
.
CK TK1 TK1 ... TKCK

Where:
  • C1, C2, ..., CK (0 ≤ C1 + C2 + ... + CK ≤ 2*105) are the number of submissions sent by teams 1 to respectively.
  • Tij, (0 < Tij ≤ 109), for valid indices i and j, are the submission times from team i. Time is measure in milliseconds from the start of the contest. For each team, times are sorted in increasing order.
You may be wondering where are the team names and the verdicts of the submissions. Well, the app receives them from another data feed. To solve the current task, you do not need them, or do you? In addition, the submission times may seem excessive, but they are actually from a progressive contest that lasts for several days ;)

Output specification

On a single line, print two integers P y Q that represent the start and end times (in milliseconds from the start of the contest) of the shortest time interval where all teams submitted at least once.  If there is no such interval, print -1 instead. If there are multiple intervals with the same shortest duration, print the one with smallest time P.
Imprima dos enteros P y Q que representen el inicio y el fin (en milisegundos desde el inicio de la competencia) del menor intervalo de tiempo donde todos los equipos realizaron al menos un envío o -1 si tal intervalo no existe. Si múltiples soluciones existieran, imprima aquella con menor valor de P.

;jsessionid=D9FD23B8F94BACCD151C9861E03D854F
On the first line, there is an integer K (1 ≤ K ≤ 105), the number of teams in the contest.

The following K lines describe the contest submission data feed consisting of all submission times from each team. The i-th line contains the submission times from the i-th team.

C1 T11 T12 ... T1C1
.
.
CK TK1 TK1 ... TKCK

Where:
  • C1, C2, ..., CK (0 ≤ C1 + C2 + ... + CK ≤ 2*105) are the number of submissions sent by teams 1 to respectively.
  • Tij, (0 < Tij ≤ 109), for valid indices i and j, are the submission times from team i. Time is measure in milliseconds from the start of the contest. For each team, times are sorted in increasing order.
You may be wondering where are the team names and the verdicts of the submissions. Well, the app receives them from another data feed. To solve the current task, you do not need them, or do you? In addition, the submission times may seem excessive, but they are actually from a progressive contest that lasts for several days ;)

Sample input

3
3 100000 200000 300000
1 180000
2 200900 520000

Sample output

180000 200900

Hint(s)

Example Input #2
4
5 10000 100000 1000000 10000000 100000000
3 70000 800000 9000000
0
4 50000 500000 3000000 50000000

Example Output #2
-1
Ejemplo de Entrada #2
4
5 10000 100000 1000000 10000000 100000000
3 70000 800000 9000000
0
4 50000 500000 3000000 50000000

Ejemplo de Salida #2
-1
Example Input #2
4
5 10000 100000 1000000 10000000 100000000
3 70000 800000 9000000
0
4 50000 500000 3000000 50000000

Example Output #2
-1