Деление
Две горнодобывающие компании совместно нашли хорошее место для добычи золота. Теперь начались жесткие переговоры: земельный участок должен быть разделен между компаниями.
Территория имеет форму квадрата и разделена на n * n единичных квадратов. Каждый малый квадрат либо пустой, либо содержит один или два месторождения золота. Вам следует разбить местность на две связные области, не обязательно одинаковых либо имеющих одинаковую площадь.
Компаниям будет лучше, если будут учтены следующие простые предложения. Граница между их областями должна начинаться в северо-западном углу, а заканчиваться в юго-восточном, и идти должна по границам единичных квадратов. Длина границы не должна превышать 2n. Каждая из двух частей должна содержать одинаковое количество месторождений золота.
Входные данные
Первая строка содержит количество тестов t. Далее идут сами тесты.
Первая строка каждого теста содержит длину n (1 ≤ n ≤ 1000) стороны участка. Следующие n строк содержат описание участка: каждая из n строк содержит n чисел. Эти числа указывают на количество месторождений золота в единичных квадратах, они равны 0, 1 или 2. Первая строка - самая северная, каждая строка выводится в направлении с запада на восток.
Выходные данные
Для каждого теста вывести:
слово IMPOSSIBLE, если возможного разделение земель не существует,
описание границы, если подходящее разделение земель существует. Вывести последовательность из не более чем 2n букв N, E, S или W, описывающих границу разделения с северо-западного угла до юго-восточного. Буквы означают, что граница идет на север, восток, юг и запад соответственно.
Если существует несколько решений, то вывести любое из них.