Решающий пень для задержек доставки

Служба доставки еды собирает данные о выполненных заказах. Для каждого заказа известна фактическая задержка курьера относительно обещанного времени и метка: был ли заказ признан проблемным.

Аналитик строит решающий пень по одному признаку delay: выбирается порог t, после чего все заказы с delay <= t получают одну метку, а заказы с delay > t — другую. Метка каждой части выбирается как наиболее частая метка среди обучающих заказов этой части.

Допустим, для порога t левая часть содержит c0 заказов с меткой 0 и c1 заказов с меткой 1. Тогда пень предсказывает 0, если c0 >= c1, иначе 1. Аналогично определяется метка правой части. Ошибка пня равна числу заказов, для которых предсказанная метка не совпала с истинной: E(t) = количество ошибок слева + количество ошибок справа.

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

Если несколько порогов дают одинаковое минимальное число ошибок, выбирается наименьший порог. Если в части одинаковое число меток 0 и 1, для этой части выбирается метка 0.

Формат ввода

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

В следующих n строках записаны два целых числа delay и label: задержка заказа в минутах и его метка проблемности. Метка 0 означает обычный заказ, метка 1 означает проблемный заказ.

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

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

В первой строке выведите четыре целых числа t left_label right_label errors:

• t — выбранный порог;
• left_label — метка при delay <= t;
• right_label — метка при delay > t;
• errors — число ошибок выбранного пня на обучающих заказах.

Во второй строке выведите q меток, предсказанных выбранным пнём для значений запроса, в исходном порядке.

Все выводимые значения являются целыми числами, округление не применяется.

Ограничения

1 <= n <= 4000.

1 <= q <= 100.

0 <= delay <= 240.

0 <= query_delay <= 240.

label равно 0 или 1.

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