Фабрика Ґаджетів
Містер Сміт — великий шанувальник гаджетів. Як тільки він зрозумів, що не може купити всі гаджети, які хоче, лише тому, що вони ще не вироблені, він вирішив побудувати власну Фабрику Гаджетів.
Фабрика Гаджетів буде розташована на місці під назвою "Кремнієва Дорога". Ця дорога є центром виробництва високотехнологічних частин, необхідних для виготовлення гаджетів. Кремнієва Дорога пряма, а фабрики розташовані дуже близько до неї, тому дорогу можна вважати віссю, а фабрики — точками на ній.
Є n частин, необхідних для виробництва гаджетів, і m фабрик, які виробляють ці частини. Містер Сміт хоче мінімізувати суму квадратів відстаней до найближчих фабрик, які виробляють кожну з необхідних частин. Допоможіть йому знайти всі точки, в яких ця сума є мінімальною.
Вхідні дані
Перша строка вхідного файлу містить цілі числа n і m (1 ≤ n ≤ 10000; n ≤ m ≤ 100000).
Наступні m рядків містять пари цілих чисел x_i і p_i, де x_i — координата i-ї фабрики, а p_i — ідентифікатор частини, яку вона виробляє (|x_i| ≤ 100000; x_i ≤ x_{i+1}; 1 ≤ p_i ≤ n).
Для кожної необхідної частини є принаймні одна фабрика, яка її виробляє.
Вихідні дані
Перша строка вихідного файлу повинна містити ціле число k - кількість точок, де може бути побудована Фабрика Гаджетів.
Наступні k рядків повинні містити ці точки у зростаючому порядку. Значення повинні бути точними з абсолютною похибкою 10^{-6}.