Prologin, the French National Computer Science Contest

Énoncé¶

Hermès vient d'annoncer une grande quête ! Elle apportera gloire et richesse à ceux qui y participeront. À travers le pays, des centaines de groupes de héros se mobilisent pour remporter le droit de mener la quête.

Seulement voilà, une fois tous les groupes rassemblés, Hermès ne peut pas se permettre d'attribuer la quête à un seul d'entre eux, cela ferait des jaloux.

Il décide donc de créer une nouvelle équipe, composée d'au moins un membre de chacun des groupes présents. Hermès considère que pour que des inconnus s'entendent bien et que leur quête soit un succès, il est nécessaire que leur âge soit le plus proche possible !

Hermès entend donc définir comme critère de sélection le plus petit intervalle d'âge qui permette à au moins un héros de chaque groupe de se présenter.

Les groupes rangent donc leurs membres du plus jeune au plus vieux, et attendent l'intervalle d'Hermès.

Fournis à Hermès un algorithme qui lui permettra de connaître les plus petits intervalles d'âge qui incluent au moins un membre de chaque groupe.

Entrée¶

L'entrée contiendra :

Sur la première ligne, un entier : $n$, le nombre de groupes.
Sur la ligne suivante, un entier : $m$, le nombre de membres par groupe.
Sur les $n$ lignes suivantes, une liste de $m$ entiers : $groupes$, représentant l'âge de chaque héros du groupe.

Sortie¶

Afficher les différents couples de valeurs définissant les plus petits intervalles d'âge incluant au moins un membre de chaque groupe. Les couples doivent être affichés du plus jeune au plus vieux.

Contraintes¶

$1 ≤ n ≤ 500$
$1 ≤ m ≤ 500$

Runtime constraints

Maximum memory usage: 9000 kilobytes
Maximum execution time: 6000 milliseconds

Input/output samples

Sample input

3
5
18 31 40 51 60
7 24 32 35 35
9 21 34 42 58

Sample output

31 34

Note

On a ici 3 groupes de 5 héros. Si l'on observe, par exemple, les plus jeunes héros de chaque groupe, la différence d'âge est de $18-9=9$ ans. Si l'on compare chaque membre de chaque groupe avec ceux des autres groupes, on trouve que le plus petit intervalle d'âge incluant au moins un membre de chaque groupe est $31 34$. En effet, on a pour les groupes, respectivement des héros agés de $31$, $32$ et $34$ ans. La différence d'âge $34-31=3$ est la plus petite trouvable.