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