题目内容

在大语言模型（LLM）训练语料清洗时，需要丢弃机械重复的“复读机”文本和包含黑名单词的文本。给定 N 篇原始文档，请你模拟清洗引擎，按顺序对每篇文档执行以下五个规则。一旦某条规则判定不通过，该文档立即被丢弃，不再进入后续规则。

规则 1：空白归一化与长度检查
将文档中所有连续的空白字符（如空格、制表符等）合并成一个空格，并删除首尾所有空白。将得到的结果记为 $s$。若 $|s| < L$ 或 $|s| > R$，即长度不在闭区间 $[L,R]$ 内，则丢弃该文档。后续步骤均基于 $s$ 进行，若文档最终保留，输出的也是 $s$。

规则 2：单词切分与小写化
对 $s$ 进行切分：所有不属于 ASCII 字母和数字的字符都视为分隔符；这里的字母和数字包括 a 到 z、A 到 Z、0 到 9。每个由连续字母数字字符组成的片段称为一个单词。按原顺序提取全部单词，并将每个单词转换为小写。

规则 3：黑名单拦截
给定 K 个黑名单词，且这些词均为小写。如果单词序列中存在某个单词与任意一个黑名单词完全相等，则丢弃该文档。该检查只比较完整单词，不进行子串匹配。例如黑名单中含有 spam 时，单词 spammer 不会被拦截。

规则 4：3-gram 复读惩罚
在单词序列中，从每个可能的位置开始，把连续三个单词组成一个 3-gram。统计每个不同 3-gram 的出现次数。如果存在任意一个 3-gram 的出现次数严格大于 M，则判定该文档为复读机文本并丢弃。若单词数量少于 3，则不会产生任何 3-gram，此规则自动通过。

规则 5：语义去重
对通过前四条规则的文档，比较其单词序列。若当前文档的单词序列与之前已经保留的某篇文档完全相同，则视为语义重复，丢弃当前文档。语义重复的文档只保留按输入顺序最早出现的一篇。

请输出经过上述全部流程后仍然保留的文档。

输入描述

输入通过标准输入读取，格式如下：

第一行包含 5 个整数：N、L、R、M、K，分别表示文档数量、规范化字符串长度的下界、规范化字符串长度的上界、3-gram 允许的最大出现次数、黑名单词数量。

若 K > 0，则第二行包含 K 个由空格分隔的黑名单词，所有黑名单词均为小写；若 K = 0，这一行不存在。

接下来共有 N 行，每行包含一篇原始文档。原始文档中可能含有空格、制表符、标点符号等字符。

输出描述

按输入顺序输出所有通过全部清洗规则的文档，每篇文档占一行。输出内容为该文档经过规则 1 后得到的规范化字符串。

样例1

输入

7 5 50 1 1
bad
Hello world hello
hello world hello
Short
This is a bad word
a b c a b c
Hello, world! hello
Hi

输出

Hello world hello
Short

说明

第 1 篇规范化后得到 Hello world hello，长度 17，在 $[5,50]$ 内。提取单词为 hello、world、hello，没有命中黑名单词 bad。单词序列长度为 3，只有 1 个 3-gram，出现 1 次，不超过 $M=1$，因此保留。

第 2 篇虽然长度也符合要求，也没有黑名单和复读问题，但单词序列与第 1 篇相同，属于语义重复，故丢弃。

第 3 篇 Short 长度为 5，刚好达到下界，单词数为 1，不产生 3-gram，且未重复，因此保留。

第 4 篇包含单词 bad，命中黑名单，直接丢弃。

第 5 篇单词序列为 a b c a b c，其中 3-gram (a,b,c) 出现 2 次，超过 $M=1$，触发复读惩罚丢弃。

第 6 篇单词序列与第 1 篇相同，语义去重丢弃。

第 7 篇 Hi 规范化后长度为 2，小于下界 5，在规则 1 被丢弃。

样例2

输入

1 1 1 0 0
A

输出

A

说明

只有 1 篇文档。规范化后得到 A，长度 1，满足 $[1,1]$ 的要求。

由于单词数量为 1，少于 3，不会产生 3-gram，因此规则 4 自动通过。

没有黑名单词，也没有之前的保留文档，所以该文档被保留并输出。

样例3

输入

5 1 20 0 2
spam bad
Buy SPAM items
abc abc
123 456 789
abc 123 abc 123
a

输出

abc abc
a

说明

第 1 篇规范化后为 Buy SPAM items，长度为 14，在 $[1,20]$ 内。提取单词为 buy、spam、items，其中 spam 在黑名单中，因此被拦截。

第 2 篇 abc abc 长度为 7，单词数为 2，没有黑名单词，也不产生 3-gram，因此保留。

第 3 篇单词序列为 123、456、789，有 1 个 3-gram，由于 $M=0$，出现 1 次已经严格大于 0，触发复读惩罚丢弃。

第 4 篇单词序列为 abc 123 abc 123，存在 3-gram 出现 1 次，同样因为 $M=0$ 被丢弃。

第 5 篇 a 长度为 1，达到下界，单词数少于 3，并且单词序列未与之前保留文档重复，因此保留。