Порог разбиения для выработки панелей

Станция хранит измерения солнечных панелей. Для части измерений значение освещённости не было получено из-за сбоя датчика и записано как NA. Такие строки не используются при построении модели.

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

Качество разбиения измеряется выигрышем уменьшения среднеквадратичной ошибки. Для группы из k выработок y_1, ..., y_k её ошибка равна SSE = sum((y_i - mean(y))^2), где mean(y) = sum(y_i) / k. Выигрыш порога равен G(t) = SSE(все строки) - SSE(левая группа) - SSE(правая группа).

После измерений поступают запросы диапазонов допустимых порогов. Для каждого запроса требуется найти допустимый порог t из указанного диапазона с наибольшим выигрышем и вывести этот порог и его выигрыш. Если допустимых порогов в диапазоне нет, выводится NONE.

При равенстве наибольшего выигрыша выбирается меньший порог.

Формат ввода

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

В следующих n строках записаны освещённость и выработка через пробел. Освещённость задаётся целым числом или строкой NA. Выработка задаётся целым числом.

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

В следующих q строках записаны два целых числа L и R — границы диапазона допустимого порога. Рассматриваются пороги t, для которых L <= t <= R.

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

Для каждого запроса выведите отдельную строку.

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

Если подходящего порога нет, выведите NONE.

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

Ограничения

1 <= n <= 4000.

Освещённость в корректной записи — целое число от 0 до 1400, либо строка NA.

Выработка — целое число от 0 до 20000.

1 <= q <= 4000.

-100 <= L <= R <= 1500.