Magasin de thés

Amateur de thés, vous avez pris vos habitudes chez un petit marchand aux stocks de thés impressionnants. Il n'y a que là que vous pouvez trouver les variétés très rares dont vous raffolez. Malheureusement la boutique de ce marchand présente un très grand défaut, il faut attendre des heures pour être servis ! La boutique ayant tellement de variétés différentes il faut à chaque fois très longtemps au marchand pour retrouver le thé qu'on lui demande. Vous décidez de l'aider.

Les thés sont numérotés par des numéros non consécutifs (leur numéro de référence international) et classés selon ce numéro sur un grand nombre d'étagères. Voici un exemple avec 8 boîtes de thés sur 3 étagères :

Etagère 1 :   1    3  10 
Etagère 2 :  25   89  90 
Etagère 3 : 124  156

Actuellement quand le marchand cherche un thé en particulier il regarde chaque numéro sur la première étagère puis sur la seconde...jusqu'à trouver portant le bon numéro. A vous de trouver un moyen plus efficace !

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 8 000 ko.

Contraintes

  • 1 <= tailleEtagere <= 20 000, le nombre de boîtes par étagère
  • 1 <= nbBoites <= 20 000, le nombre total de boîtes.
  • 1 <= nbClients <= 20 000, le nombre de clients.
  • 0 <= numero <= 108, le numéro d'un thè.

Entrée

Sur la première ligne un entier tailleEtagere le nombre de boîtes par étagère.

Sur la seconde ligne un entier nbBoites, le nombre total de boîtes.

Sur la troisième ligne nbBoites entiers, les numéros de référence de chacun des thés, donnés en ordre croissant. Il n'y a pas de doublons.

Sur la quatrième ligne un entier nbClients, le nombre de clients de la journée.

Sur la cinquième ligne nbClients entiers, les numéros des thés demandés par chaque client.

Sortie

Pour chaque client vous devez indiquer afficher deux entiers : le numéro de l'étagère et la position dans cette étagère où se trouve le thé qu'il souhaite acheter.

Si le thé demandé n'existe pas en stock, vous devez simplement afficher -1.

Les numéros des étagères et les positions démarrent à la valeur 1.

Exemple

entrée :

3
8
1 3 10 25 89 90 124 156
4
89 1000 1 156

sortie :

2 2
-1
1 1
3 2

Commentaires

Le premier thé est sur la 2ème étagère à la position 2. Le deuxième n'existe pas. Le troisième est sur la 1ère étagère en 1ère position. Le dernier thé est sur la 3ème étagère en 2ème position.


Source : http://www.france-ioi.org/