Послідовність триангуляції
Тріангуляція багатокутника — це процес проведення відрізків між його вершинами, щоб розділити багатокутник на трикутники. Ці відрізки мають знаходитись всередині багатокутника, не перетинаючись між собою, і торкатися сторін багатокутника лише у вершинах. Наприклад:
На прикладі жирною лінією показані межі багатокутника, а тонкими — тріангуляції. При тріангуляції багатокутника з n вершинами утворюється (n-2) трикутника.
Трикутна послідовність тріангуляції формується, якщо, починаючи з певної вершини і рухаючись навколо багатокутника по його вершинах, записувати кількість трикутників, інцидентних цим вершинам. Для наведеного прикладу такими послідовностями будуть (починаючи зверху, зліва):
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
Напишіть програму, яка за послідовністю з n натуральних чисел визначить, чи є вона трикутною послідовністю тріангуляції багатокутника з n вершинами. Якщо відповідь позитивна, виведіть список трикутників у тріангуляції в лексикографічному порядку.
Вхідні дані
Перша строка містить кількість тестів p (1 ≤ p ≤ 1000).
Кожен тест складається з одного рядка, що містить номер тесту k, кількість чисел у послідовності n (4 ≤ n ≤ 20), а також самі n цілих чисел послідовності у відповідному порядку, розділені пробілом.
Вихідні дані
Для кожного тесту виведіть кілька рядків. Якщо вхідна послідовність НЕ є трикутною для n-кутника, виведіть номер тесту k, пробіл і велику літеру N. Інакше в першому рядку виведіть номер тесту k, пробіл і велику літеру Y. Далі виведіть n - 2 рядки, що містять індекси вершин трикутників у тріангуляції, по одному трикутнику в рядку, індекси вершин виводьте у зростаючому порядку. Трикутники спочатку слід відсортувати лексикографічно. Якщо k < l < m - індекси вершин одного трикутника, а r < s < t - індекси вершин другого, то перший трикутник передує другому в лексикографічному порядку, якщо:
k < r OR (k == r AND l < s) OR (k == r AND l == s AND m < t)