Задача A. Ответы к тесту ≡

Условие

Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.

Поскольку Гена не подготовился к тесту, он решил схитрить. Для этого он подговорил P шушанчиков, чтобы они прошли тест до него. Каждый шушанчик запомнил, как он отвечал на каждый из вопросов, и сколько баллов получил.

По этим данным Гена должен определить правильные ответы.

Формат входного файла

В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:

• В первой строке описываются ответы, данные шушанчиком. Они задаются строкой длинной Q, состоящей из символов + (ASCII 43) или - (ASCII 45) для ответов "Да" или "Нет" соответственно. На i-ой позиции строки находится ответ на i-ый вопрос.
• Во второй строке содержится целое число — количество баллов.

Формат выходного файла

В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.

Ограничения

1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15

Примеры тестов

1 2
+-
0

-+

3 4
--++
3
----
1
---+
2

+-++

Задача B. Слово из кубиков ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Задача C. Уравнение для 5 класса ≡

Условие

Уравнение для пятиклассников представляет собой строку длиной 5 символов. Второй символ строки является либо знаком '+' (плюс) либо '-' (минус), четвёртый символ — знак '=' (равно). Из первого, третьего и пятого символов ровно два являются цифрами из диапазона от 0 до 9, и один — буквой x, обозначающей неизвестное.

Требуется решить данное уравнение относительно x.

Формат входного файла

Формат выходного файла

Примеры тестов

x+5=7

2

3-x=9

-6

Задача D. Максимальный перепад ≡

Условие

Недавно в главном офисе картографической службы Ландшафтии случился пожар. Сгорел архив, хранящий таблицы с перепадами высот в различных регионах страны. Для восстановления этой информации требуется заново посчитать перепады высот по сохранившимся картам.

Карта региона представляет собой матрицу размером N x N клеток, в каждой клетке которой содержится средняя высота определённого района над уровнем моря. Максимальным перепадом высот называется максимальная величина, на которую отличаются средние высоты двух районов, соседних на карте по горизонтали или по вертикали. Требуется по карте региона определить максимальный перепад высот в нем.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
1 1 1
1 2 1
1 2 3

2

Задача E. Автомобильные номера ≡

Условие

При расследовании дорожно-транспортных происшествий часто возникают проблемы с розыском автомобилей, водители которых покинули место происшествия.

Получение свидетельских показаний — непростая работа. Ситуация осложняется тем, что очень часто свидетели могут только приблизительно вспомнить номер автомобиля. При этом с большой вероятностью опрашиваемый может перепутать порядок цифр или букв в номере.

По полученному от свидетеля происшествия номеру, подсчитайте, сколько различных номеров может получиться из него перестановкой букв и/или цифр, а также выведите все такие номера.

Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать.

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

Формат входного файла

Входной файл содержит одну строку, которая представляет собой корректный автомобильный номер.

Формат выходного файла

Примеры тестов

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача F. Сплошной кафель ≡

Условие

Плитка кафеля имеет форму квадрата размером 1 × 1, раскрашенного в один из цветов, заданных буквами от "a" до "z".

Если замостить квадратную область размером N × N разноцветными плитками, то могут образоваться горизонтальные или вертикальные одноцветные полосы длиной N плиток.

По описанию области следует определить цвета горизонтальных и вертикальных полос.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4
owww
owow
wwow
oowo

NO

3
ibi
ibi
ibi

bi

Задача G. Судьба математика ≡

Условие

Любимая девушка одного математика сообщила ему номер своего телефона. Как истинный представитель своей профессии, он тут же забыл этот номер, однако успел заметить и запомнить целый ряд соотношений между цифрами. Дальнейшая судьба математика зависит от того, сможет ли он по этим соотношениям определить достаточно узкое множество подходящих номеров, чтобы успеть обзвонить их за приемлемое время.

В городе, где они живут, телефонные номера состоят из 6 цифр от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).

Между цифрами номера возможны 6 видов отношений: >, <, =, <=, >=, <>. Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1<2
3=1
3>4

12000

Задача H. Два компьютера ≡

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров T_i секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5 7 10 3 5 6

16

Problem I. Sudoku Checker ≡

Statement

The puzzle game of Sudoku is played on a board of N² × N² cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N².

The sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct position, fill all empty cells so that the final position is still correct.

This game is fairly popular in the Internet, and there are many sites which allow visitors to solve puzzles online. Such sites always have a subroutine to determine a correctness of a given position.

You are to write such a routine.

Input file format

Output file format

Constraints

Sample tests

2
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 1

CORRECT

2
2 1 3 0
3 2 4 0
1 3 2 4
0 0 0 1

INCORRECT

Problem J. Hot-keys ≡

Statement

Input file format

Input file contains number of captions N followed by N lines with captions.

Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

Sample tests

3
yes
no
cancel

&yes
&no
&cancel

4
abc
bca
acb
aaaa

&abc
&bca
a&cb
aaaa