Шаг градиента для прогноза кешбэка

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

Для чека с числом акционных товаров \(x_i\) модель предсказывает кешбэк \(\hat y_i = wx_i + b\). Некоторые чеки ещё не обработаны программой лояльности: для них во второй таблице указано NA. Такие чеки не участвуют в вычислении функции потерь и градиента.

Пусть \(S\) — множество чеков, для которых известен кешбэк, а \(k=|S|\). Функция потерь с L2-регуляризацией имеет вид

\[L(w,b)=\frac{1}{k}\sum_{i\in S}(wx_i+b-y_i)^2+\lambda w^2.\]

Необходимо выполнить ровно один шаг градиентного спуска с коэффициентом обучения \(\eta\):

\[w_{new}=w-\eta\left(\frac{2}{k}\sum_{i\in S}(wx_i+b-y_i)x_i+2\lambda w\right),\]

\[b_{new}=b-\eta\left(\frac{2}{k}\sum_{i\in S}(wx_i+b-y_i)\right).\]

Вывести \(w_{new}\) и \(b_{new}\) в этом порядке через пробел. Каждое число округляется до четырёх знаков после точки по правилу ближайшего значения, а при ровно половинном случае — в сторону удаления от нуля. Если после округления получается ноль, он выводится без знака минус.

При равенстве каких-либо значений предпочтение не выбирается: оба обновлённых параметра всегда выводятся в порядке \(w_{new}\), затем \(b_{new}\).

Формат ввода

В первой строке дано целое число \(n\) — число чеков в каждой из двух таблиц.

Во второй строке через пробел даны четыре вещественных числа: начальные параметры \(w\), \(b\), коэффициент обучения \(\eta\) и коэффициент регуляризации \(\lambda\).

В следующих \(n\) строках дана первая таблица. Каждая строка содержит идентификатор чека receipt_id и целое число promo_items — количество товаров по акции в чеке.

В следующих \(n\) строках дана вторая таблица. Каждая строка содержит идентификатор чека receipt_id и либо целое число cashback, либо строку NA.

Идентификаторы чеков в каждой таблице уникальны. Множества идентификаторов в двух таблицах совпадают. Хотя бы для одного чека кешбэк известен, поэтому \(k>0\).

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

Выведите два числа w_new и b_new через пробел, каждое ровно с четырьмя знаками после точки.

Ограничения

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

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

\(0 \le promo_items \le 200\).

\(0 \le cashback \le 1000\), если вместо него не указано NA.

\(-20 \le w,b \le 20\).

\(0.001 \le \eta \le 1\).

\(0 \le \lambda \le 5\).

В обеих таблицах содержится ровно по \(n\) строк.