Problem G
Grab a Graph

Bash and Chikapu are strongly addicted to…graphs. They enjoy playing with graphs so much that they skip meals quite often. Today, they are going to a supermarket. But instead of grabbing some snack, they grab some graphs.

Bash only likes weighted undirected graph with small numbers of vertices and edges. More precisely, Bash only likes weighted undirected graphs with at most $72$ vertices and at most $2\, 525$ edges.

Chikapu only likes weighted undirected graph with even fewer edges. More precisely, Chikapu only likes weighted undirected graphs with at most $88$ vertices and at most $214$ edges.

Bash and Chikapu give Mr. Graph Maker — the owner of the supermarket — an integer $A$ between $0$ and $10^{18}$, inclusive. They ask him for two graphs where the number of shortest paths from vertex $1$ to vertex $2$ is exactly $A$. (Each graph must have at least two vertices, and vertices are numbered starting at $1$.) To challenge Mr. Graph Maker a little bit more, both graphs must not contain self-loops or duplicate edges. Of course, the first graph must satisfy Bash’s preference and the second graph must satisfy Chikapu’s preference (in terms of number of vertices and edges, as above).

Please help Mr. Graph Maker create these graphs.

Notes

Given a graph $G = (V, E)$, a path from vertex $u$ to vertex $v$ is defined as a sequence of edges $(a_0, a_1), (a_1, a_2), \ldots , (a_{k-1}, a_ k)$ where:

• $a_0 = u$,

• $a_ k = v$,

• $(a_{i-1}, a_ i) \in E$.

The weight of a path is the sum of the weights of all edges on that path.

A shortest path from $u$ to $v$ is a path with smallest weight from $u$ to $v$.

Two paths are considered different iff their sequences of edges are different.

Input

The input contains at most $101$ lines. Each line (except the last one) contains an integer $A$ $(0 \leq A \leq 10^{18})$ representing a test case. The last line contains the number $-1$, which is not a test case.

Output

For each test case,

• If it is impossible to create a graph which Bash asks for, print a single line containing the word ‘NO’.

• Otherwise, print a line containing the word ‘YES’. On the next line, print $2$ integers $N$ and $M$ $(2 \leq N \leq 72, 0 \leq M \leq 2\, 525)$ — the number of vertices and edges of Bash’s graph. On each of the next $M$ lines, print $3$ integers $u$, $v$ and $c$, representing an edge connecting vertices $u$ and $v$ with weight $c$. $(1 \le u, v \le N, 1 \le c \le 10^9)$.

• If it is impossible to create a graph which Chikapu asks for, print a single line containing the word ‘NO’.

• Otherwise, print a line containing the word ‘YES’. On the next line, print $2$ integers $N$ and $M$ $(2 \leq N \leq 88, 0 \leq M \leq 214)$ — the number of vertices and edges of Chikapu’s graph. On each of the next $M$ lines, print $3$ integers $u$, $v$ and $c$, representing an edge connecting vertices $u$ and $v$ with weight $c$. $(1 \le u, v \le N, 1 \le c \le 10^9)$.

The graphs must not contain any self-loops or duplicate edges, and the number of shortest paths from $1$ to $2$ must equal $A$.

Explanation for the first example

The graph given to Bash in sample 1:

The graph given to Chikapu in sample 1:

The graph given to both Bash and Chikapu in sample 2:

1
3
-1

YES
2 1
1 2 100
YES
3 2
1 3 1000
3 2 10000
YES
5 6
1 3 1
3 2 1
1 4 1
4 2 1
1 5 1
5 2 1
YES
5 6
1 3 1
3 2 1
1 4 1
4 2 1
1 5 1
5 2 1