User ainta likes trees. This time he is going to make an undirected tree with $*n*$ vertices numbered by integers from $1$ to $*n*$. The tree is weighted, so each edge of the tree will have some integer weight.

Also he has an array $*t*$: $*t*[1], *t*[2], ..., *t*[*n*]$. At first all the elements of the array are initialized to $0$. Then for each edge connecting vertices $*u*$ and $*v*$ ($*u* < *v*$) of the tree with weight $*c*$, ainta adds value $*c*$ to the elements $*t*[*u*], *t*[*u* + 1], ..., *t*[*v* - 1], *t*[*v*]$ of array $*t*$.

Let's assume that $*d*(*u*, *v*)$ is the total weight of edges on the shortest path between vertex $*u*$ and vertex $*v*$. User ainta calls a pair of integers $*x*, *y*$ ($1 ≤ *x* < *y* ≤ *n*$) good if and only if $*d*(*x*, *y*) = *t*[*x*] + *t*[*x* + 1] + ... + *t*[*y* - 1] + *t*[*y*]$.

User ainta wants to make at least good pairs, but he couldn't make a proper tree. Help ainta to find such a tree.

Input

The first line contains a single integer $*n*$ ($5 ≤ *n* ≤ 10^{5}$).

Output

Print $*n* - 1$ lines containing the description of the edges. The $*i*$-th line should contain three space-separated integers $*u*_{*i*}, *v*_{*i*}, *c*_{*i*}$ ($1 ≤ *u*_{*i*} < *v*_{*i*} ≤ *n*; 1 ≤ *c*_{*i*} ≤ 10^{5}$) — two vertices connected by the edge, and the weight of the edge.

Next print lines containing the good pairs. The $*k*$-th line should contain two space-separated integers $*x*_{*k*}$ and $*y*_{*k*}$ ($1 ≤ *x*_{*k*} < *y*_{*k*} ≤ *n*$). Of course, $*x*_{*k*}, *y*_{*k*}$ must be a good pair. All pairs should be distinct — that is, for all $*j*, *k*$ , $*x*_{*j*} ≠ *x*_{*k*}$ or $*y*_{*j*} ≠ *y*_{*k*}$ must be satisfied.

If there are many correct solutions, print any of them.

Note

$⌊*x*⌋$ is the largest integer not greater than $*x*$.

You can find the definition of a tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)

You can also find the definition of the shortest path by the following link: http://en.wikipedia.org/wiki/Shortest_path_problem

The tree and the array $*t*$ in the sample output look like this: