Pour un graphe simple non orienté pondéré $G$ composé de $N$ sommets (numérotés de $1$ à $N$) et de $M$ arêtes, on définit le score de forêt comme suit :

1. Soient $F_1, F_2, F_3, \ldots, F_M$ chacun un graphe sans arêtes composé des $N$ sommets numérotés de $1$ à $N$.
2. Soient $e_1, e_2, \ldots, e_M$ les arêtes de $G$ triées par poids croissant. Pour $i = 1, 2, \ldots, M$, on effectue successivement l'opération suivante :
   • Trouver le plus petit entier positif $j$ tel que l'ajout de $e_i$ à $F_j$ ne crée pas de cycle, puis ajouter $e_i$ à $F_j$. Ajouter $e_i$ signifie ajouter une arête reliant les sommets $u_i$ et $v_i$ dans $F_j$, où $u_i$ et $v_i$ sont les extrémités de $e_i$.
3. Le score de forêt du graphe $G$ est le plus grand $i$ tel que $F_i$ contienne au moins une arête.

Vous avez pour mission de générer un graphe $G$ avec exactement $k$ comme score de forêt et au plus $2024$ sommets, où $k$ est un entier positif.

Ce problème étant trop facile pour vous, il vous est apparu plus intéressant de trouver un $G$ satisfaisant les conditions supplémentaires suivantes :

• Si $N$ est le nombre de sommets de $G$, alors le nombre d'arêtes est $(2N-2)$.
• On peut colorier $(N-1)$ des arêtes de $G$ en rouge et les $(N-1)$ autres en bleu de sorte que le sous-graphe constitué uniquement des arêtes rouges soit un arbre, et de même pour les arêtes bleues.

Étant donné $k$, trouvez et affichez un graphe $G$ satisfaisant ces conditions.

Entrée

La première ligne contient un entier $k$ ($2 \le k \le 12$).

Sortie

Affichez sur la première ligne le nombre de sommets $N$ du graphe $G$ ($2 \le N \le 2024$).

Sur les $(2N-2)$ lignes suivantes, affichez sur la $i$-ème ligne trois entiers $a_i$, $b_i$, $c_i$ séparés par des espaces ($1 \le a_i, b_i \le N$ ; $a_i \neq b_i$ ; $1 \le c_i \le 10^9$). Cela signifie qu'il existe une arête de poids $c_i$ reliant les sommets $a_i$ et $b_i$.

$G$ doit satisfaire les conditions suivantes :

• Tous les poids des arêtes sont distincts, c'est-à-dire que les $c_i$ sont tous différents.
• Les $N-1$ premières arêtes affichées forment un arbre. De même, les $N-1$ arêtes suivantes forment un arbre.
• Il n'existe pas de paire de sommets reliée par deux arêtes ou plus directement.
• Le score de forêt de $G$ est égal à $k$.

Exemples

Entrée 1

3

Sortie 1

5
1 2 8
2 3 1
3 4 2
4 5 5
1 3 6
3 5 4
5 2 7
2 4 3

Remarque

Voici un exemple de réponse correcte pour $k=3$.

Le graphe ci-dessus est constitué de deux arbres disjoints comme on peut le voir dans la figure ci-dessous.

En calculant le score de forêt, on obtient $3$ comme ci-dessous. Les arêtes rouges appartiennent à $F_1$, les arêtes bleues à $F_2$, les arêtes vertes à $F_3$.