Ділення#5545
Дві гірничодобувні компанії знайшли перспективне місце для видобутку золота. Тепер вони ведуть напружені переговори: земельну ділянку потрібно поділити між компаніями.
Територія має форму квадрата і складається з n \times n одиничних квадратів. Кожен з цих квадратів може бути або порожнім, або містити одне чи два родовища золота. Ваше завдання — розділити цю територію на дві зв'язані області, які не обов'язково повинні бути однаковими за розміром або площею.
Компанії бажають дотримуватися наступних умов. Межа між їхніми ділянками повинна починатися в північно-західному куті і закінчуватися в південно-східному, проходячи по межах одиничних квадратів. Довжина цієї межі не повинна перевищувати . Кожна з двох частин повинна містити однакову кількість родовищ золота.
Перший рядок містить кількість тестів . Далі йдуть самі тести.
Перший рядок кожного тесту містить довжину (1 \le n \le 1000) сторони ділянки. Наступні рядків описують ділянку: кожен з рядків містить чисел. Ці числа вказують на кількість родовищ золота в одиничних квадратах і можуть бути , або . Перший рядок є найпівнічнішим, а кожен рядок виводиться із заходу на схід.
Для кожного тесту виведіть:
слово IMPOSSIBLE, якщо неможливо здійснити поділ земель,
опис межі, якщо можливий поділ існує. Виведіть послідовність з не більше ніж літер N, E, S або W, що описують межу поділу з північно-західного кута до південно-східного. Літери означають, що межа йде на північ, схід, південь і захід відповідно.
Якщо існує декілька рішень, виведіть будь-яке з них.
Приклад 1