Prologin, the French National Computer Science Contest

Énoncé¶

La porte sur laquelle vous faite maintenant face semble être dirigée par un système informatique bien complexe. Des écrans se situent de part et d'autre de la pièce, avec des inscriptions en vert sur fond noir qui défilent. Vous reconnaissez tout de suite ces inscriptions : Il s'agit de la Matriks ! Pourtant, vous êtes convaincus d'en être venu à bout il y a peu. Pourquoi la porte peut-elle bien être bloquée ?

Vous réalisez soudainement le problème et vous vous tapez le front : bien heureux d'avoir réussi à déchiffrer la Matriks et d'avoir sauvé Sion, vous avez laissé votre interface de connexion à la Matriks ouverte sans vous déconnecter ! N'ayant pas le temps de revenir en arrière, vous allez devoir tenter de vous déconnecter à distance depuis les interfaces présentes dans cette pièce.

Vous avez accès au code intégral de la Matriks, représenté sous la forme d'une liste de $N$ nombres entiers (possiblement négatifs). Petit rappel de la terminologie Matriks : on appelle une "clé" de la Matriks toute sous-liste de la Matriks, c'est-à-dire toute séquence de nombres contigus au sein de la Matriks. On pourra représenter une clé de la Matriks par deux entiers naturels, correspondants à l'index du premier et du dernier nombre de la clé dans la Matriks. Les index commencent à 0, ainsi la Matriks en elle-même peut être représentée par le couple $(0, N-1)$.

Après une longue réflexion, vous vous souvenez de toute les clés qui doivent vous permettre d'accéder à votre compte. Cependant, vous devez les renseigner par ordre lexicographique afin de pouvoir établir la connexion.

On dit qu'une clé $A$ est inférieure par ordre lexicographique à une clé $B$ si :

$A$ est un préfixe de $B$, ou
à la première position $i$ où les deux clés diffèrent : $A_i$ < $B_i$, ou
$A$ et $B$ sont exactement les mêmes clés, mais $A$ se situe plus tôt dans la Matriks.

Par exemple, ces trois clés sont triées par ordre lexicographique : 1 3 4, 1 3 4 1, 1 5.

Entrée¶

L’entrée contiendra :

Sur la première ligne, un entier : N, la longueur du code la Matriks.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : M, le code de la Matriks.
Sur la ligne suivante, un entier : C, le nombre de clés.
Sur les lignes suivantes, une liste de C éléments : cles, les clés à trier.
- Une ligne par élément de la liste : séparés par des espaces, un entier gauche (index de la borne gauche de la clé), et un entier droite (index de la borne droite de la clé).

Sortie¶

Afficher tout d'abord les clés triées par ordre lexicographique.

Vous devez afficher une clé par ligne, la plus petite par ordre lexicographique sur la première ligne, et la plus grande par ordre lexicographique sur la dernière ligne.

Chaque clé doit être représentée sous la forme de deux entiers séparés par un espace : L'index de l'élément le plus à gauche de la clé dans la Matriks, ainsi que l'index de l'élément le plus à droite de la clé dans la Matriks.

Enfin, pour ne pas reproduire la même erreur, n'oubliez pas de vous déconnecter en affichant "Déconnexion".

Contraintes¶

$1 \le N \le 10\,000$
$1 \le C \le 10\,000$
$-1\,000\,000 \le M_i \le 1\,000\,000$

Contraintes de performance¶

$1 \le N \le 100\,000$
$1 \le C \le 100\,000$

Runtime constraints

Maximum memory usage: 1000 kilobytes
Maximum execution time: 1000 milliseconds

Input/output samples

Sample input

10
3 1 4 1 5 9 2 6 5 3
6
1 4
1 2
3 4
1 1
3 3
5 6

Sample output

1 1
3 3
1 2
1 4
3 4
5 6
Déconnexion

Note

Voici les 6 clés que vous devez trier :

(1, 4) : 1 4 1 5
(1, 2) : 1 4
(3, 4) : 1 5
(1, 1) : 1
(3, 3) : 1
(5, 6) : 9 2

Une fois triées par ordre lexicographique, vous devez obtenir ceci :

(1, 1) : 1
(3, 3) : 1
(1, 2) : 1 4
(1, 4) : 1 4 1 5
(3, 4) : 1 5
(5, 6) : 9 2

Si les clés (1, 1) et (3, 3) ont exactement le même contenu, la clé (1, 1) est considérée comme lexicographiquement inférieure, car elle se situe plus tôt dans la Matriks. La clé (1, 2) est un préfixe de la clé (1, 4), et est donc considérée comme lexicographiquement inférieure à celle-ci. À la première position où les clés (1, 4) et (3, 4) diffèrent, c'est-à-dire la deuxième position, la clé (1, 4) possède un 4 et la clé (3, 4) possède un 5. La clé (1, 4) est donc lexicographiquement inférieure à la clé (3, 4).

N'oubliez pas de vous déconnecter !