29. 1984 (2.0)

Вы - модератор чата, вам регулярно приходится удалять сообщения, содержащие нецензурную лексику. Дан список стоп-слов $D,10<|D|<10^4,1\leq|D_i|\leq10^3$, вхождение любой комбинации которых должно подвергать сообщение блокировке. Также вам даны сообщения $M,10<|M|<10^4,1\leq|M_i|\leq10^6$. Вам нужно определить для каждого из них, должно быть оно удалено или нет.

Отличие от более простой версии задачи заключается в ограничениях на входные данные.

В первой строке задается два числа $n, 10 \leq n \leq 10^4$ $-$ количество стоп-слов и $m, 10 \leq m \leq 10^4$ $-$ количество сообщений.

Далее идёт $n$ строк, на каждой из которых задается стоп-слово $D_{i}, 1\leq|D_{i}|\leq10^3$, после чего на следующих $m$ строках задаются сообщения $M_i,1\leq|M_i|\leq10^6$, для каждого из которых необходимо определить, должно оно быть удалено или нет. Гарантируется, что суммарная длина всех $m$ строк не превышает $10^6$.

В качестве ответа ваша программа должна вывести $m$ строк, на каждой из которых для сообщения, которое должно быть удалено, нужно вывести слово DELETE, в противном случае - слово KEEP.