День Народження

У Стаса незабаром день народження, і з цієї нагоди він вирішив влаштувати грандіозну вечірку. Звісно, Стас розіслав запрошення всім своїм знайомим. Очікується велика кількість гостей, тому планується грандіозне шоу.

Усі гості сповістили Стаса, в який час вони прийдуть на вечірку, та о котрій будуть змушені її залишити. Проаналізувавши цю інформацію, Стас склав розклад прибуття та відбуття гостей, адже він хоче, щоб все пройшло ідеально, і належним чином підготуватись. Вечірка буде продовжуватись $N$ хвилин. Стас знає, що рівно K гостей зможуть прийти до початку вечірки. Далі, протягом усієї вечірки кожної хвилини або прибуде новий гість, або ж хтось із присутніх її залишить.

Докладаючи великих зусиль, Стасу вдалося отримати згоду свого улюбленого Відомого Артиста на виконання однієї пісні. Для нього на вечірці буде побудована величезна сцена, перед якою стоятиме нескінченна кількість стільців, пронумерованих послідовними натуральними числами, починаючи з одиниці.

На жаль, є одна проблема. Відомий Артист має дуже щільний графік і точно не знає, в який момент часу він зможе приїхати виступати. Тому Стас вирішив зайняти гостей іншими розвагами, а коли Артист приїде і буде готовий розпочати, швиденько розсадить усіх гостей на підготовлені стільчики перед сценою.

Розсаджування відбувається таким чином:

Спочатку Стас визначає порядок розсадження. Гостям пропонується розсаджуватися по одному саме в тій послідовності, яку визначив наш герой.

Однак, кожен друг Стаса має свої примхи. Наприклад, кожен має своє улюблене число. Тому, коли хтось обирає, на який стілець йому сісти, він намагається обрати стілець зі своїм улюбленим номером. Якщо він вже зайнятий, гість ображається, але вирішує сісти на стілець, який стоїть одразу за ним. Якщо зайнятим буде і той стілець, гість образиться ще сильніше, але буде шукати наступний вільний стілець. Можна вважати, що цей процес відбувається миттєво. У підсумку, загальну образу гостя на Стаса можна виразити різницею номерів зайнятого і бажаного місць. Стас – прекрасний товариш, тому йому відоме улюблене число кожного з його знайомих.

Виступ Артиста триватиме рівно одну мить, тому Стасу не потрібно турбуватися, що комусь під час виконання пісні потрібно буде піти, або прийде новий гість, якого потрібно буде посадити. Звісно, Стас хоче мінімізувати сумарну образу гостей.

Стасу необхідно для кожної хвилини вечірки розрахувати мінімальну сумарну образу, якщо потрібно буде розсадити усіх наразі присутніх гостей. Для нього це виявилося заважким завданням, тому він просить Вас допомогти.

Вхідні дані

У першому рядку вхідного файлу містяться два натуральних числа $N$ і $K$ - тривалість вечірки в хвилинах та кількість гостей, що прийдуть до початку вечірки.

Наступний рядок містить $K$ натуральних чисел, розділених пробілом – улюблені числа гостей, які присутні до початку вечірки.

У кожному з $N$ наступних рядків йде розклад прибуття-відбуття гостей. Рядки містять по два числа, $T$ та $X$. Якщо $T$ дорівнює $1$, це означає, що в відповідну хвилину прийде новий гість, улюблене число якого дорівнює $X$. Інакше, вечірку буду змушений залишити гість, який мав число $X$ за улюблене; гарантується, що в такому разі хоча б один гість з улюбленим числом $X$ був присутній на вечірці.

Усі числа у вхідному файлі натуральні та не перевищують $5\cdot 10^4$. T приймає значення $0$ або $1$.

Вихідні дані

У першому рядку виходного файлу виведіть через пробіл $N$ чисел - мінімальну сумарну образу після розсадження всіх присутніх гостей для кожної хвилини.

Приклади

Примітка

До початку вечірки прийдуть гості, з улюбленими числами 1, 1 і 2. Вечірка починається, і у першу хвилини приходить ще один гість з числом 2. Маємо чотири гостя. Оптимальною може бути, наприклад, така розсадка:

Спочатку ми пропонуємо зайняти свої місця друзям с числами 1 та 2. Вони без проблем по черзі займають їх, не ображаючись на Стаса. Далі запропонуємо зайняти місце гостю з номером 1. Оскільки стільчики 1 та 2 зайняті, він займає третій стілець, ображаючись на Стаса на величину 3 - 1 = 2. Останнім сідає гість з числом 2, займає 4 місце та ображається на 4 - 2 = 2. Сумарна образа усіх гостей дорівнює 4.

О другій хвилині вечірку залишить гість з улюбленим числом 1, і залишаться лише люди з числами 1, 2, 2.

Оцінювання

• У $15\%$ тестів - усі числа натуральні, не перевищують $5$

• У $35\%$ тестів - гості не залишають вечірки (усі $T$ рівні одиниці)