Шаг роста потерь при настройке кормления

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

Для выбранного животного на шаге t вычисляется средняя квадратичная ошибка потерь:

L_t = (1 / k) · Σ(план_i − факт_i)^2,

где суммирование идёт по всем кормлениям этого животного на шаге t, у которых известна фактически выданная масса, а k — число таких кормлений. Строки с символом - вместо фактической массы в расчёте не участвуют.

Необходимо найти первый шаг t, для которого L_t строго больше L_(t−1). Если такого шага нет, требуется сообщить об этом. Сравнение выполняется по точным значениям дробей, без промежуточного округления. При равенстве потерь на соседних шагах ростом это не считается. Если рост происходит на нескольких шагах, выводится наименьший номер такого шага.

Формат ввода

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

В следующих n строках записаны четыре значения: animal step planned actual:

• animal — идентификатор животного;
• step — номер шага настройки;
• planned — рекомендованная масса корма в граммах;
• actual — фактически выданная масса в граммах или символ -, если запись отсутствует.

В последней строке задан идентификатор animal животного, указанного в запросе.

Для животного из запроса существуют записи с известной фактической массой на каждом шаге от 0 до некоторого T включительно. Поэтому для каждого его шага знаменатель k не меньше 1.

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

Выведите STEP t, где t — первый шаг, на котором потери выросли по сравнению с предыдущим шагом.

Если потери ни разу не выросли, выведите NONE 0.

Округление не выполняется: выводятся ровно слово STEP или NONE и целый номер шага.

Ограничения

• 1 ≤ n ≤ 4000;
• 0 ≤ step ≤ 3999;
• 0 ≤ planned ≤ 50000;
• если actual не равно -, то 0 ≤ actual ≤ 50000;
• длина идентификатора animal составляет от 1 до 20 символов;
• идентификаторы состоят из строчных латинских букв, цифр и символа _;
• для животного из запроса номера шагов с известными данными образуют непрерывный отрезок от 0 до T;
• строка запроса совпадает хотя бы с одним идентификатором из записей.