Выбор датчика для разбиения тепличных наблюдений

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

Нужно выбрать один датчик из датчиков, перечисленных в запросе. Каждый датчик задаёт бинарное разбиение наблюдений по штатной границе: temperature — 25 градусов, humidity — 70 процентов, co2 — 800 ppm, light — 10000 люкс. Наблюдения со значением не выше границы попадают в левую группу, остальные — в правую.

Для каждого датчика отдельно считаются два прироста неоднородности: по индексу Джини и по энтропии. Для группы с долями классов p₁ и p₂ индекс Джини равен G = 1 - p₁² - p₂², а энтропия равна H = -p₁ log₂(p₁) - p₂ log₂(p₂). Слагаемое вида 0 log₂(0) считается равным нулю. Прирост для меры I равен I(родитель) - (L / N) I(левая) - (R / N) I(правая), где N — число наблюдений с известным значением данного датчика, а L и R — размеры левой и правой групп среди этих наблюдений.

Пропуск значения датчика обозначается строкой NA. При расчёте прироста данного датчика наблюдения с NA для этого датчика полностью игнорируются, включая родительскую группу. Если у датчика нет известных значений или одна из его групп пуста, оба его прироста считаются равными нулю.

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

Если оба критерия выбрали один датчик, требуется вывести SAME и его имя. Иначе требуется вывести DIFFERENT, затем имя датчика, выбранного индексом Джини, и имя датчика, выбранного энтропией.

Формат ввода

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

В следующих n строках записаны пять значений: temperature humidity co2 light label. Первые четыре значения являются целыми числами или строкой NA. Последнее значение равно Healthy или Stress.

В последней строке записано целое число q и q имён датчиков через пробел. Имена датчиков могут быть только temperature, humidity, co2, light и не повторяются.

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

Если оба критерия выбрали один датчик, выведите строку SAME name.

Если критерии выбрали разные датчики, выведите строку DIFFERENT gini_name entropy_name.

Ограничения

1 ≤ n ≤ 4000.

1 ≤ q ≤ 4.

Температура при отсутствии пропуска находится в пределах от -30 до 60.

Влажность при отсутствии пропуска находится в пределах от 0 до 100.

Концентрация CO2 при отсутствии пропуска находится в пределах от 300 до 3000.

Освещённость при отсутствии пропуска находится в пределах от 0 до 120000.

Длина каждой строки наблюдения не превышает 40 символов. Имена датчиков имеют длину от 3 до 11 символов.