З'єднання островів
Громадянська війна в океані Байтландії завершилася. Два острови Байтландії вирішили об'єднатися, утворивши Об'єднане Королівство Байтландії. Одним з перших питань, яке розглядає новообраний уряд, є транспорт.
До війни кожен з 2 островів мав ідеальну транспортну мережу. На будь-якому острові кожне місто було з'єднане поїздом з кожним іншим містом. З'єднання були двосторонніми. Під час війни деякі залізничні лінії були пошкоджені, і тому поїзди на цих лініях були призупинені. На будь-якому острові не більше ніж 15 поїздів були призупинені. Окрім відновлення роботи пошкоджених поїздів, уряд має створити міжострівні поромні з'єднання. Пороми з'єднають кожне місто X з кожним містом Y, за умови, що X і Y не знаходяться на одному острові. Пересування між містами на одному острові буде здійснюватися лише поїздами.
У Байтландії все є двійковим, включаючи ціни на квитки на поїзди та пороми. Квиток коштує або 0, або 1 одиницю валюти. Уряд вирішив не змінювати ціни на квитки на поїзди, які не були пошкоджені під час війни. Він призначить вартість квитків для поїздів, призупинених під час війни, та для всіх поромних ліній. Пишаючись своїми математичними здібностями, байтландці вирішили розробити систему квитків так, щоб для будь-яких 3 різних міст X, Y і Z,
C(X, Y) + C(Y, Z) ≥ C(X , Z)
де C(X, Y) — це вартість квитка з міста X до міста Y (поїздом, якщо вони належать одному острову, або поромом інакше).
Вам надано опис островів Байтландії, ваша мета — визначити призначення вартості, якщо це можливо.
Вхідні дані
Ваша програма буде протестована на одному або кількох тестових випадках. Перша строка вхідних даних міститиме одне ціле число T, кількість тестових випадків (1 ≤ T ≤ 100). Далі йдуть тестові випадки, кожен тестовий випадок — це опис обох островів (один за іншим). Опис одного острова починається з одного рядка, що містить одне ціле число C_k, яке представляє кількість міст на цьому острові, за яким слідують C_k рядків, кожен з яких містить C_k символів (1 ≤ C_k ≤ 100). Кожен символ — це '0', '1' або 'x'. j-й символ i-го рядка — це вартість квитка на поїзд з міста i до міста j на цьому острові. Ціна 'x' означає, що це одна з призупинених залізничних ліній. Кожна C_k на C_k таблиця гарантовано симетрична (table[i][j] = table[j][i] для кожного різного i та j), і кожна таблиця матиме діагональ з '0' (table[i][i] = '0' для кожного різного i), також кожна таблиця міститиме не більше ніж 30 'x' (15 різних поїздів, оскільки кожен поїзд буде згаданий двічі в таблиці).
Зверніть увагу, що вхідні дані можуть містити 3 різних міста на одному острові, і поїзди, що їх з'єднують, не призупинені, і ці 3 міста не задовольняють описану умову вище.
Вихідні дані
Для кожного тестового випадку, якщо немає способу виконати призначення вартостей, що задовольняють описані вище умови, виведіть на одному рядку NO (без лапок). Інакше виведіть YES (без лапок) на першому рядку, за яким слідують C_1+C_{2 }рядків, кожен з яких містить C_1+C_2 символів (C_1 — це кількість міст на першому острові, а C_2 — кількість міст на другому острові). j-й символ на i-му рядку — це вартість проїзду з міста i до міста j (поїздом, якщо вони належать одному острову, або поромом інакше). У вихідних даних міста на першому острові нумеруються від 1 до C_1 (включно), а міста на другому острові нумеруються від C_1+1 до C_1+C_2 (включно). Якщо існує більше ніж одне правильне рішення, виведіть будь-яке з них.
Зверніть увагу, що ви не можете змінювати вартість, зазначену у вхідних даних, і вихідна таблиця повинна бути симетричною.