Настройка модели погодной станции

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

Для оценки точки росы используется линейная модель \(\hat y=w_0+w_1x\), где \(x\) — температура, \(y\) — точка росы. Значение NA в таблице температур означает пропуск измерения: такая станция не участвует в обучении модели.

В начале \(w_0=0\) и \(w_1=0\). Необходимо выполнить ровно \(m\) шагов пакетного градиентного спуска с коэффициентом обучения \(\alpha=0.0001\). На каждом шаге используются веса, полученные после предыдущего шага. Для всех станций без пропуска пусть их количество равно \(k\). Тогда

\[ E_i=w_0+w_1x_i-y_i, \] \[ g_0=\frac{2}{k}\sum E_i,\qquad g_1=\frac{2}{k}\sum E_ix_i, \] \[ w_0:=w_0-\alpha g_0,\qquad w_1:=w_1-\alpha g_1. \]

Если температуры у нескольких станций совпадают, все соответствующие строки учитываются в суммах отдельно. Гарантируется, что идентификаторы станций не повторяются внутри каждой таблицы и каждая станция из первой таблицы присутствует во второй. Гарантируется, что хотя бы у одной станции температура не равна NA.

Формат ввода

В первой строке даны два целых числа n и m — число станций и число шагов градиентного спуска.

В следующих n строках записана первая таблица: идентификатор станции station_id и температура temperature. Температура является целым числом или строкой NA.

В последних n строках записана вторая таблица: идентификатор станции station_id и целая точка росы dew_point.

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

Выведите два числа: итоговые значения w0 и w1 через пробел.

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

Ограничения

\(1\le n\le 4000\).

\(1\le m\le 2000\).

Идентификатор станции состоит из латинских букв, цифр и символа _, его длина составляет от 1 до 12 символов.

Температура, если она не равна NA, является целым числом от \(-50\) до \50.

Точка росы является целым числом от \(-70\) до \50.