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

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

Нужно построить первый узел дерева решений только по записям выбранных видов животных. Кандидатами на признак являются ration, enclosure и shift. Поле animal используется только для отбора записей по запросу и не может быть выбрано признаком.

Для множества записей \(S\) неоднородность целевой метки timely измеряется индексом Джини: \(G(S)=1-\sum_c p_c^2\), где \(p_c\) — доля записей класса \(c\) в \(S\), а классы yes и no. Для признака \(X\) его уменьшение неоднородности равно \(Gain(X)=G(S)-\sum_v \frac{|S_v|}{|S|}G(S_v)\), где \(S_v\) содержит записи со значением \(v\) признака \(X\). Требуется вывести имя признака с наибольшим значением Gain.

Значение - означает неизвестное значение признака и считается обычной отдельной категорией. В запросе гарантированно есть хотя бы одна подходящая запись, поэтому деления на ноль не возникает. Если наибольшее значение Gain достигается у нескольких признаков, выводится лексикографически меньшее имя признака.

Формат ввода

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

В следующих n строках содержатся пять строковых полей через пробел: animal ration enclosure shift timely.

Затем дано целое число q — число видов животных в запросе.

В следующих q строках дано по одному значению animal. Для расчёта используются только записи, у которых поле animal совпадает хотя бы с одним значением из запроса.

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

Выведите одно имя признака: ration, enclosure или shift.

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

Ограничения

• 1 <= n <= 4000;
• 1 <= q <= 20;
• каждое имя animal имеет длину от 1 до 20 символов и состоит из строчных латинских букв;
• каждое значение ration, enclosure, shift имеет длину от 1 до 20 символов и состоит из строчных латинских букв либо равно -;
• timely равно yes или no;
• значения animal в запросе попарно различны;
• каждый вид из запроса встречается хотя бы в одной из n записей.