456. Запускайте гуся

Не решаласьЛёгкая

Студенты школы мобильных разработчиков создали поисковый движок, который ориентируется на ключевые слова. Например, пользователь ищет информацию о гусях, и поисковому движку выдаётся перечень из nn статей с названием сайта и кратким описанием статьи. Если на сайте в кратком описании статей суммарно не менее kk раз упомянуто ключевое слово, то, скорее всего, сайт создан для обхода поискового робота и может содержать некачественный контент. Учтите, что если ключевое слово является частью другого слова, это не учитывается как отдельное упоминание. Робот скрывает такие сайты из поисковой выдачи. Определите количество отфильтрованных сайтов и выведите их названия.

Формат ввода

В первой строке содержатся два целых числа: nn — количество статей, kk — количество упоминаний слова goose для применения фильтра (1n105,0k1061 \le n \le 10^5, 0 \le k \le 10^6).

В следующих nn парах строк содержатся:

  • siteisite_i

    — название сайта: строка, состоящая не более чем из 2020 строчных символов английского алфавита;

  • messageimessage_i

    — краткое описание статьи: строка, состоящая не более чем из 100100 строчных символов английского алфавита и пробелов.

Все названия сайтов различны. На одном сайте может быть несколько статей.

Гарантируется, что суммарная длина всех сообщений не превосходит 2×1062 \times 10^6.

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

В первой строке выведите nn — количество отфильтрованных сайтов. В следующих nn строках выведите в алфавитном порядке названия сайтов, скрытых из поиска.

Примечание

Рассмотрим Пример 1.

Всего в запросе 22 уникальных сайта:

  • Android;
  • iOS.

Рассмотрим краткие описания статей:

  • gooseberries are very tasty00 упоминаний, так как подстроки не считаются;
  • the goose11 упоминание;
  • goose is the coolest11 упоминание.

Суммарное количество упоминаний для каждого сайта:

  • Android: 0+1=10 + 1 = 1 — сайт скрывается;
  • iOS: 1=11 = 1 — сайт скрывается.

Ограничения

Ограничение времени

1 с

Ограничение памяти

256 МБ

Пример 1

Ввод
3 1
android
gooseberries are very tasty
ios
the goose
android
goose is the coolest
Вывод
2
android
ios

Пример 2

Ввод
3 2
android
gooseberries are very tasty
ios
the goose
android
goose is the coolest
Вывод
0

Теги

Нужно войти, чтобы отправить решение.Войти