题目背景

为了帮助读者从大量历史文章中找到有用内容，bloggo 搜索引擎支持一种称为邻近搜索的查询方式。

与只查找单个单词不同，邻近搜索可以查找多个指定单词在文档中彼此靠近出现的段落。查询还可以递归嵌套，从而描述更加复杂的搜索条件。

请实现这种邻近搜索，并输出质量最高的至多十个匹配段落。

题目描述

给定若干篇文档 documents 和一个邻近搜索查询 query。

每篇文档是一个字符串。文档由英文字母、空格以及若干标点符号组成。

单词

一个单词是一个极大的连续英文字母序列。

也就是说：

• 单词只包含英文字母；
• 单词不能是另一个更长连续字母序列的一部分；
• 标点符号和空格都会分隔单词。

在每篇文档中，将所有单词从左到右依次编号为：

$$0,1,2,\ldots$$

这些编号称为单词的位置编号。

匹配单词时不区分大小写。

段落

一篇文档中的一个段落使用一对整数 $(a,b)$ 表示，其中：

$$0\le a\le b.$$

它表示从位置编号为 $a$ 的单词开始，到位置编号为 $b$ 的单词结束的连续原文子串。

若 $a=b$，则该段落只包含一个单词。

段落必须从一个完整单词的第一个字符开始，并在一个完整单词的最后一个字符结束。位于首尾单词之间的空格和标点符号均原样保留。

查询语法

查询符合以下文法：

Query -> Word | "(" Query " " Near " " Query ")"
Near  -> "+" Num
Num   -> Digit | Digit Digit | Digit Digit Digit
Digit -> "0" | "1" | ... | "9"

其中：

• Word 是一个或多个英文字母组成的单词；
• Num 由一到三位十进制数字组成，允许存在前导零；
• 二元查询中的空格、加号和括号均严格按照上述格式出现。

例如：

word
(can +000 we)
((the +099 people) +999 by)

均是合法查询。

查询的匹配规则

单词查询

若查询本身是一个单词 $W$，它匹配文档中所有内容等于 $W$ 的单个单词段落。

匹配不区分大小写。

例如，查询 HIS 可以同时匹配文档中的 His、his 和 HIS。

邻近查询

设一个查询为：

(X +n Y)

其中 $X,Y$ 也是查询，$n$ 是 + 后的整数。

假设：

• 段落 $(a,b)$ 匹配查询 $X$；
• 段落 $(c,d)$ 匹配查询 $Y$。

若两个段落重叠，则它们一定可以组合。

若两个段落不重叠，则它们之间至多可以隔着 $n$ 个完整单词。具体来说：

• 若 $b<c$，必须满足

$$c-b\le n+1;$$

• 若 $d<a$，必须满足

$$a-d\le n+1.$$

满足条件时，组合得到的新段落为：

$$\left(\min(a,c),\max(b,d)\right).$$

注意：

• $X$ 对应的段落可以位于 $Y$ 对应段落的左侧或右侧；
• 两个段落可以重叠；
• 同一个最终段落可能由多种组合方式得到，但在搜索结果中只出现一次。

段落质量与排序

段落 $(p,q)$ 的宽度定义为：

$$q-p.$$

宽度越小，段落质量越高。

所有匹配段落按照以下优先级排序：

1. 宽度较小的段落优先；
2. 宽度相同时，来自编号较小文档的段落优先；
3. 宽度和文档编号均相同时，在文档中出现得较早的段落优先。

同一篇文档中的“出现得较早”，按照段落首个单词的位置编号判断。

不同结果必须对应不同的文档或不同的单词区间，但它们的文本内容可以完全相同。

只输出排序后的前十个匹配段落。若匹配段落不足十个，则输出全部匹配段落。

结果字符串格式

每个结果字符串必须采用：

DOC_ID START_INDEX [PASSAGE_TEXT]

其中：

• DOC_ID 是文档从 $0$ 开始的编号；
• START_INDEX 是段落第一个字符在该文档中的从 $0$ 开始的字符下标；
• PASSAGE_TEXT 是文档中的原始段落文本；
• DOC_ID 与 START_INDEX 之间恰好有一个空格；
• START_INDEX 与左方括号 [ 之间恰好有一个空格；
• 除 PASSAGE_TEXT 自身包含的空格外，不添加其他空格。

例如：

1 25 [we can]

表示段落来自文档 $1$，段落第一个字符的下标为 $25$，原文内容为 we can。

输入格式

第一行包含一个整数 $D$，表示文档数量。

接下来 $D$ 行，每行完整描述一篇文档。文档中的空格和标点符号均属于文档内容。

最后一行包含字符串 query，表示邻近搜索查询。

由于文档本身可能以空格开头或结尾，实现时应使用能够保留整行内容的方式读取文档。

输出格式

第一行输出一个整数 $R$，表示输出的匹配段落数量，其中：

$$0\le R\le 10.$$

接下来 $R$ 行，按照质量从高到低依次输出结果字符串：

DOC_ID START_INDEX [PASSAGE_TEXT]

结果字符串中的空格、标点和大小写均须与文档原文及规定格式完全一致。

数据范围

对于所有测试数据：

• $1\le D\le 50$；
• 每篇文档的长度在 $1$ 到 $50$ 之间；
• 文档中只包含：
  • 小写英文字母 a 到 z；
  • 大写英文字母 A 到 Z；
  • 空格；
  • 标点符号 ,、;、.、!、?、-、(、)；
• $1\le |\text{query}|\le 50$；
• query 一定符合题目给出的查询文法。

样例 1

输入

19
But in a larger sense we can not dedicate --
we can not consecrate -- we can not hallow this
ground. The brave men, living and dead, who
struggled, here, have consecrated it far above
our poor power to add or detract. The world will
little note, nor long remember, what we say here,
but can never forget what they did here. It is
for us, the living, rather to be dedicated here
to the unfinished work which they have, thus
far, so nobly carried on. It is rather for us
to be here dedicated to the great task remaining
before us -- that from these honored dead we take
increased devotion to that cause for which they
here gave the last full measure of devotion --
that we here highly resolve that these dead
shall not have died in vain; that this nation
shall have a new birth of freedom; and that
this government of the people, by the people,
for the people, shall not perish from the earth.
(can +000 we)

输出

3
0 22 [we can]
1 0 [we can]
1 25 [we can]

解释

查询要求 can 和 we 之间不能隔着其他单词。共有三个符合条件的段落。

样例 2

输入

19
But in a larger sense we can not dedicate --
we can not consecrate -- we can not hallow this
ground. The brave men, living and dead, who
struggled, here, have consecrated it far above
our poor power to add or detract. The world will
little note, nor long remember, what we say here,
but can never forget what they did here. It is
for us, the living, rather to be dedicated here
to the unfinished work which they have, thus
far, so nobly carried on. It is rather for us
to be here dedicated to the great task remaining
before us -- that from these honored dead we take
increased devotion to that cause for which they
here gave the last full measure of devotion --
that we here highly resolve that these dead
shall not have died in vain; that this nation
shall have a new birth of freedom; and that
this government of the people, by the people,
for the people, shall not perish from the earth.
this

输出

3
1 43 [this]
15 34 [this]
17 0 [this]

解释

单词 this 在所有文档中一共出现三次。

样例 3

输入

19
But in a larger sense we can not dedicate --
we can not consecrate -- we can not hallow this
ground. The brave men, living and dead, who
struggled, here, have consecrated it far above
our poor power to add or detract. The world will
little note, nor long remember, what we say here,
but can never forget what they did here. It is
for us, the living, rather to be dedicated here
to the unfinished work which they have, thus
far, so nobly carried on. It is rather for us
to be here dedicated to the great task remaining
before us -- that from these honored dead we take
increased devotion to that cause for which they
here gave the last full measure of devotion --
that we here highly resolve that these dead
shall not have died in vain; that this nation
shall have a new birth of freedom; and that
this government of the people, by the people,
for the people, shall not perish from the earth.
((the +099 people) +999 by)

输出

4
17 19 [the people, by]
17 23 [people, by the]
17 31 [by the people]
17 19 [the people, by the people]

解释

匹配段落之间可以相互重叠，最终得到的不同单词区间分别作为不同结果输出。

样例 4

输入

19
But in a larger sense we can not dedicate --
we can not consecrate -- we can not hallow this
ground. The brave men, living and dead, who
struggled, here, have consecrated it far above
our poor power to add or detract. The world will
little note, nor long remember, what we say here,
but can never forget what they did here. It is
for us, the living, rather to be dedicated here
to the unfinished work which they have, thus
far, so nobly carried on. It is rather for us
to be here dedicated to the great task remaining
before us -- that from these honored dead we take
increased devotion to that cause for which they
here gave the last full measure of devotion --
that we here highly resolve that these dead
shall not have died in vain; that this nation
shall have a new birth of freedom; and that
this government of the people, by the people,
for the people, shall not perish from the earth.
((TO +20 (tO +20 tO)) +20 ((TO +20 tO) +20 To))

输出

7
4 15 [to]
7 27 [to]
8 0 [to]
10 0 [to]
10 21 [to]
12 19 [to]
10 0 [to be here dedicated to]

解释

单词匹配不区分大小写。