Масштабирование тренировок в градиентном шаге

На школьной спартакиаде для прогноза результата забега используется линейная модель. Признак x — число тренировок участника перед стартом, целевая величина y — результат в секундах. Прогноз модели равен ŷ = w·x + b.

Часть участников не сообщила число тренировок. В строке таких участников вместо значения признака записано NA. Такие строки не участвуют ни в функции потерь, ни в вычислении градиента. Их результаты забега известны, но для обучения модели не используются.

Перед одним шагом градиентного спуска организаторы могут заменить каждый известный признак x на c·x, где c — значение из запроса. Начальные коэффициенты w и b, а также скорость обучения не меняются. Для каждого запроса требуется выполнить ровно один шаг градиентного спуска и сравнить полученные коэффициенты с коэффициентами после одного шага без масштабирования, то есть при c = 1.

На строках с известным числом тренировок определяется среднеквадратичная ошибка MSE = (1/m) · Σ(ŷᵢ - yᵢ)², где m — число строк без NA. После замены признака на x' = c·x градиенты равны ∂MSE/∂w = (2/m) · Σ((w·x'ᵢ + b - yᵢ)·x'ᵢ) и ∂MSE/∂b = (2/m) · Σ(w·x'ᵢ + b - yᵢ). Коэффициенты обновляются одновременно: w_new = w - η·∂MSE/∂w, b_new = b - η·∂MSE/∂b, где η = p / 1000000.

Для каждого запроса выведите SAME, если оба коэффициента после шага в точности равны коэффициентам при c = 1, и CHANGED иначе. Затем выведите найденные w_new и b_new. При равенстве коэффициентов сравнение выполняется по точным значениям до округления.

Формат ввода

В первой строке даны два целых числа n и q — число записей о забегах и число запросов.

Во второй строке даны три целых числа w, b и p — начальные коэффициенты модели и числитель скорости обучения η = p / 1000000.

В следующих n строках даны два значения: число тренировок x и результат забега y. Вместо x может быть записано NA.

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

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

Для каждого запроса выведите отдельную строку из трёх значений: слово SAME или CHANGED, затем w_new и b_new.

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

Ограничения

1 ≤ n ≤ 4000.

1 ≤ q ≤ 30.

-100 ≤ w ≤ 100.

0 ≤ b ≤ 10000.

1 ≤ p ≤ 10000.

В каждой строке данных x равно NA либо целому числу от 0 до 100.

100 ≤ y ≤ 10000.

1 ≤ c ≤ 20.

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