Le dernier recensement des vaches Jersey et Holstein donne aux vaches de Wisconsin trois stalles dans Barn of Representatives. Les Jersey contrôlent actuellement le comité de redécoupage de l’État. Elles veulent trois circonscriptions de même taille, leur garantissant de gagner dans au moins deux.

Wisconsin a $3*K$ ($1 \le K \le 60$) villes de $1,000$ vaches, numérotées $1..3*K$, chacune avec un nombre connu de Jersey ($0..1,000$). Répartissez l’État en trois circonscriptions de $K$ villes, avec une majorité de Jersey dans au moins deux.

Tous les jeux d’entrée ont une solution.

Entrée

• Ligne $1$ : un entier $K$.

• Lignes $2..3*K+1$ : un entier par ligne, le nombre de Jersey de chaque ville. La ligne $i+1$ donne le recensement de la ville $i$.

Sortie

• Lignes $1..K$ : $K$ lignes de numéros de villes de la première circonscription, un par ligne.

• Lignes $K+1..2K$ : $K$ lignes de numéros de villes de la deuxième circonscription, un par ligne.

• Lignes $2K+1..3K$ : $K$ lignes de numéros de villes de la troisième circonscription, un par ligne.

Exemples

Entrée 1

2
510
500
500
670
400
310

Sortie 1

1
2
3
6
5
4

Remarque

D’autres solutions sont possibles. 2 3 ne serait PAS gagné par les Jersey, puisqu’elles représentent exactement la moitié des vaches.

Auteur du problème : Coaches, 2004