A Triangulation of a polygon is a set of lines between vertices of the polygon that divide the polygon into triangles. The lines must be inside the polygon and may not intersect each other except at vertices of the polygon. For example:
In the examples, the heavy line is the outline of the polygon and the lighteg lines give the triangulation. In each case a triangulation of a polygon with n vertices will result in (n-2) triangles.
The triangle count sequence of a triangulation is obtained by starting at some vertex, proceeding around the polygon and for each vertex of the polygon recording the number of triangles of the triangulation incident of that vertex. In the examples above the triangle count sequences starting at the top (left) are:
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
Write a program which takes as input a sequence of n positive integers and determines whether the sequence is the triangle count sequence of a polygon of n vertices. If so, list the triangles of the triangulation in lexicographical order.
The first line contains the number of data sets p (1 ≤ p ≤ 1000). Each data set shoul be processed identically and indenpendently.
Each data set consists of a single line in input. It cintains the data set number k followed be the number, n (4 ≤ n ≤ 20) of integers in the sequence, followed by n integers of the sequence in order, all separated by a single space.
For each data set there may be multiple lines of output. If the input sequence is NOT the triangle count sequence of a polygon of n vertices, the single output line consists of the data set number k, followed by a single space followed by the (captail) letter N. Otherwise (the input sequence is the triangle count sequence of a polygon of n vertices), the first output line consists of the data set number k, followed by a single space followed by the (captail) letter Y. Following this line are (n-2) lines each containing the indices of the vertices of a triangle of the triangulation, one triangle per line, with the vertex indices in increasing order. The triangle should be sorted in lexicographic order least first. That is, k < l < m are the vertex indices of one triangle and r < s < t are the vertex indices of another, then the first precedes the second in lexicographical order if:
k < r OR (k == r AND l < s) OR (k == r AND l == s AND m < t)