Признаки для дерева отзывов

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

Идентификатор признака наличия слова равен word. Идентификатор признака автора с именем ivan равен name:ivan. Признак word принимает значение 1, если заданное слово является одним из слов отзыва, и 0 иначе. Признак name:ivan принимает значение 1 только у отзывов автора ivan.

Для каждого признака нужно вычислить уменьшение неоднородности после разбиения на группы со значениями 0 и 1. Для группы, содержащей долю положительных отзывов p, неоднородность Джини равна G = 1 - p^2 - (1-p)^2, а энтропия равна H = -p·log2(p) - (1-p)·log2(1-p). Слагаемое вида 0·log2(0) считается равным нулю. Неоднородность пустой группы считается равной нулю.

Если в исходной группе n отзывов, а после разбиения размеры групп равны n0 и n1, то уменьшение неоднородности равно I(исходная) - n0/n·I(группа 0) - n1/n·I(группа 1), где I — соответственно Джини или энтропия. Требуется независимо выбрать признак с наибольшим уменьшением Джини и признак с наибольшим уменьшением энтропии.

Формат ввода

В первой строке даны целое число n и заданное слово target.

В следующих n строках записаны имя автора author, метка label и поле words.

label равно 0 для отрицательного отзыва и 1 для положительного. Поле words содержит слова отзыва через запятую без пробелов либо единственный символ -, если текст отзыва отсутствует. При отсутствии текста признак word имеет значение 0.

Формат вывода

Выведите в первой строке идентификатор признака, выбранного по уменьшению Джини.

Выведите во второй строке идентификатор признака, выбранного по уменьшению энтропии.

Округление не выполняется: выводятся только идентификаторы признаков.

Если уменьшения неоднородности отличаются не более чем на 10^-12, они считаются равными. При равенстве выбирается лексикографически меньший идентификатор признака.

Ограничения

1 ≤ n ≤ 4000.

Длина target составляет от 1 до 12 строчных латинских букв.

Длина имени автора составляет от 1 до 12 строчных латинских букв.

label равно 0 или 1.

Поле words равно - либо содержит от 1 до 20 слов. Длина каждого слова составляет от 1 до 12 строчных латинских букв.