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

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

Нужно выбрать категориальный признак, который будет использован в корне дерева решений для предсказания результата good или bad. Рассматриваются признаки session, surface и weather.

Для признака X вычисляется информационный выигрыш Information Gain:

IG(X) = H(Y) - sum по значениям v признака X от (|S_v| / n) * H(S_v),

где Y — все результаты, S_v — тренировки со значением v, а энтропия множества результатов S равна H(S) = -sum по классам c от p_c * log2(p_c). Здесь p_c — доля класса c в S, а слагаемое 0 * log2(0) считается равным 0. Значения - означают, что характеристика тренировки неизвестна, и считаются обычной категорией.

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

Формат ввода

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

Следующие n строк содержат первую таблицу в формате:

run_id session surface weather

Затем следуют n строк второй таблицы в формате:

run_id result

Идентификаторы во второй таблице могут располагаться в произвольном порядке. Каждый идентификатор из первой таблицы встречается во второй таблице ровно один раз.

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

Выведи имя признака с наибольшим информационным выигрышем: session, surface или weather.

Округление не применяется, так как выводится точное имя признака.

Ограничения

1 <= n <= 4000.

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

session имеет одно из значений easy, tempo, interval, long, -.

surface имеет одно из значений road, track, trail, treadmill, -.

weather имеет одно из значений sun, rain, wind, snow, -.

result имеет одно из значений good, bad.

Длина каждого значения характеристики не превышает 10 символов. Пустых строк и отсутствующих идентификаторов нет.