Лінкори
Ви, напевно, знайомі з паперовою версією гри "Морський бій", але дозвольте нам її описати: кожна головоломка складається з 10-на-10 сітки квадратів, у якій таємно розміщено 10 різних кораблів. Один з цих кораблів має довжину 4 квадрати, два мають довжину 3 квадрати, три мають довжину 2 квадрати, а решта чотири кораблі займають по 1 квадрату. Жодні два кораблі не можуть перекриватися або бути суміжними, навіть по діагоналі. Єдині підказки щодо розташування кораблів - це набір сум рядків і стовпців, надрукованих зліва і знизу сітки. Нижче наведено приклад головоломки "Морський бій" та її рішення.
Рисунок 1
При розробці головоломки "Морський бій" ви повинні переконатися, що існує єдине рішення для заданих сум рядків і стовпців. Іноді суми з боків є всім, що потрібно для забезпечення унікального рішення (як у прикладі вище), але іноді потрібно вказати один або кілька квадратів у сітці, щоб виключити всі, крім одного рішення (як у прикладі нижче).
Рисунок 2
Ці вказані квадрати можуть бути одного з семи типів: вода, внутрішня частина корабля, лівий кінець горизонтального корабля, верхній кінець вертикального корабля, правий кінець горизонтального корабля, нижній кінець вертикального корабля та 1-квадратний корабель. Вони показані на верхній частині наступної сторінки. Символи під кожним квадратом будуть використовуватися для вашого виводу. Зверніть увагу, що останній символ - це велика літера 'O', а не нуль; також зверніть увагу, що 'X' - велика літера, але 'w' і 'v' - малі.
Рисунок 3
Ваше завдання таке: маючи набір сум рядків і стовпців, ви повинні знайти мінімальну кількість вказаних квадратів, необхідних для забезпечення унікального рішення. Якщо це число більше ніж 2, ви повинні відхилити головоломку як занадто неоднозначну.
Вхідні дані
Вхідний файл починається з цілого числа n, що вказує кількість тестових випадків. Кожен тестовий випадок складається з двох рядків: перший містить десять сум рядків, а другий - десять сум стовпців.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку, за яким слідує загальна кількість можливих рішень для заданих сум рядків і стовпців (це число ніколи не перевищує 12000), за яким слідує мінімальна кількість вказаних квадратів, необхідних для забезпечення унікального рішення. Якщо це число більше ніж 2, відобразіть фразу занадто неоднозначно.
Інакше виведіть розташування "найкращого" квадрата(ів), які можуть бути використані для забезпечення унікального рішення, за яким слідує тип квадрата, який слід використовувати, використовуючи символи, показані на Рисунок 3. У випадку одного квадрата, "найкращий" квадрат - це квадрат з найменшим номером рядка, розв'язуючи будь-які зв'язки, вибираючи той, що має найменший номер стовпця. Після цього, якщо є вибір між типом квадрата, використовуйте лексикографічно перший, де лексикографічний порядок показаний на Рисунок 3, з "водою" як лексикографічно першим типом квадрата, за яким слідує "внутрішня частина корабля" і так далі. У випадку двох квадратів, виведіть пару, перший квадрат якої є найкращим серед усіх перших квадратів, розв'язуючи зв'язки, вибираючи той, що має найкращий другий квадрат. Усі номери рядків і стовпців починаються з 1.