Triangulation and Triangle Counts

A triangulation of a polygon is a set of segments joining vertices that cuts the polygon into triangles. Every segment has to lie inside the polygon, and no two segments may meet anywhere except at a vertex. Triangulating a polygon with $n$ vertices always produces $n-2$ triangles.

Start at one vertex, walk around the boundary, and write down how many triangles touch each vertex in turn. The list you get is the triangle count sequence. All three sequences below are triangle count sequences. A and B come from a polygon with 6 vertices, C from a polygon with 12 vertices.

• A: 1 3 1 3 1 3
• B: 2 2 1 4 1 2
• C: 1 2 3 2 1 6 1 2 3 2 1 6

Given a sequence of $N$ positive integers, write a program that decides whether some triangulation has that sequence as its triangle count sequence. If one does, print all of its triangles.

The first line contains the number of test cases $P$. ($1 \le P \le 1000$)

Each of the next $P$ lines holds one test case. The first integer on a line is the test case number $K$, and the second is the length of the sequence $N$. ($4 \le N \le 20$) The remaining $N$ integers are the triangle count sequence, and all of them are positive.

For each test case print the test case number $K$, a space, and the verdict. Print the capital letter N when no triangulation has the given sequence as its triangle count sequence, and the capital letter Y when one does.

After a Y, print the triangles on the next $N-2$ lines, one per line. Vertices are numbered 1 through $N$ in the order the sequence gives them, and the three vertex numbers of one triangle are printed in increasing order. Sort the triangles lexicographically. When $k < l < m$ is one triangle and $r < s < t$ is another, the first comes before the second if

k<r OR (k==r AND l<s) OR (k==r AND l==s AND m<t)

At most one triangulation fits a given sequence, so the output is fixed.