Бор

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K−1). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A₁ рублей. Те, у кого совпали первые две цифры числа — получают A₂ рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A₃ рублей. И так далее. Угадавшие все число полностью получают Am рублей. При этом если игрок угадал t первых цифр, то он получает A_t рублей, но не получает призы за угадывание t−1, t−2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

Входные данные
В первой строке задаются числа N (количество телезрителей, сделавших свои ставки, 1 ≤ N ≤ 100000), M (длина чисел 1 ≤ M ≤ 10) K (основание системы счисления 2 ≤ K ≤ 10). В следующей строке записаны M чисел A₁, A₂, ..., A_M, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1 ≤ A₁ ≤ A₂ ≤ ... ≤ A_M ≤ 100000). В каждой из следующих N строк записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

Выходные данные
В первой строке выведите искомое число (если решений несколько — выведите любое из них), а во второй строке — сумму, которую при назывании телеведущей первого числа придется выплатить в качестве выигрыша.

Примеры

№	Входные данные	Выходные данные
1	10 3 2 1 3 100 000 000 001 010 100 100 100 100 110 111	011 6
2	1 1 10 100 0	1 0

У вас есть q запросов и мультимножество A, изначально содержащее только число 0. Запросы бывают трёх видов:

• + x — добавить в мультимножество A число x.
• - x — удалить одно вхождение числа x из мультимножества A. Гарантируется, что хотя бы одно число x в этот момент присутствует в мультимножестве.
• ? x — вам даётся число x, требуется вычислить максимальное значение побитового исключающего ИЛИ (также известно как XOR) числа x и какого-нибудь числа y из мультимножества A.

Мультимножество — это множество, в котором разрешается несколько одинаковых элементов.

Входные данные:
В первой строке входных данных содержится число q (1 ≤ q ≤ 200000) — количество запросов, которые требуется обработать Василию.

Каждая из последующих q строк входных данных содержит один трёх символов «+», «-» или «?» и число x_i (1 ≤ x_i ≤ 10⁹). Гарантируется, что во входных данных встречается хотя бы один запрос «?».

Обратите внимание, что число 0 всегда будет присутствовать в мультимножестве.

Выходные данные:
На каждый запрос типа «?» выведите единственное целое число — максимальное значение побитового исключающего ИЛИ для числа x_i и какого-либо числа из мультимножества A.

Пример:
 

Входные данные	Выходные данные
10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11	11 10 14 13

Дана игра для двоих игроков со строками.

Задан набор, состоящий из n непустых строк. Во время игры два игрока вместе строят слово, изначально это слово пустое. Игроки ходят по очереди. За свой ход игрок должен дописать в конец слова одну букву так, чтобы полученное слово было префиксом хотя бы одной строки из заданного набора. Проигрывает тот, кто не может сделать ход.

По задданому набору строк определите, кто будет победителем, если оба игрока будут играть оптимально.

Входные данные:
Первая строка содержит целое число n (1 ≤ n ≤ 10⁵).
Каждая из n следующих строк содержит непустую строку из заданного набора. Суммарная длина всех строк из набора не превышает 10⁵. Все строки из набора состоят только из строчных латинских букв.

Выходные данные:
Если победит игрок, который ходит первым, то выведите «First», иначе выведите «Second» (кавычки выводить не нужно).

Примеры:
 

Входные данные	Выходные данные
3 a b c	First
1 ab	Second

Блейз отправляет приказы на перемещение своим войскам, собранным из жителей одной из теней. К сожалению, они не понимают амберский язык, поэтому Блейзу приходится отправлять им сообщения на их родном языке.
В этом и заключается проблема: Амберийский принц плохо знает орфографию этого языка, поэтому иногда он делает ошибки в словах, но не более одной ошибки в слове.
В языке очень много слов, поэтому если в слове изменится хотя бы одна буква, то его смысл может кардинально измениться. Если армия не правильно поймет приказ, то вся военная кампания может провалиться. Поэтому Блейзу очень важно проверять правильность в написании слов. Он решил попросить вас помочь ему.
Вы должны создать программу, которая будет выводить в лексикографическом порядке все возможные слова, которые Блейз мог пытаться написать с учетом того, что он мог ошибиться 1 раз.