Masha-forgetful

题意翻译

**【题目描述】** Masha 认识了一个新朋友并且获得了他的电话号码 $s$。她想要尽快地记住它。电话号码是一个长度为 $m$，由 $0\sim 9$ 构成的字符串。电话号码有可能以 $0$ 开始。 Masha 已经知道了 $n$ 个电话号码（所有的电话号码长度都为 $m$）。如果新的电话号码 $s$ 能拆分成几段并且存在于她已经知道的电话号码中，她能够更容易得记住新号码。每一个段的长度都必须大于等于 $2$，否则 Masha 会因为有太多的段而混淆。 举个例子，Masha 需要记住的号码 $s$ 是 $\texttt{12345678}$，并且她知道 $n=4$ 个号码：$\texttt{12340219}$，$\texttt{20215601}$，$\texttt{56782022}$，$\texttt{12300678}$。你可以用在 $s$ 中拆分成 $3$ 段：$\texttt{1234}$ 在第一个号码中，$\texttt{56}$ 在第二个号码中，$\texttt{78}$ 在第三个号码中。当然还有其它分解 $s$ 的方法。 Masha 想要你来帮她，她想让你把电话号码 $s$ 拆分成几个长度大于等于 $2$ 的字符串，并且在她知道的电话号码中存在。如果有多个答案，请输出其中的任意一个。 **【输入格式】** 输入数据的第一行包含一个整数 $t(1\le t\le 10^4)$，表示测试数据组数。 在每一组数据之前都有一行空行。每组数据的开头是两个整数：$n$ 和 $m(1 \le n,m \le 10^3)$，分别表示 Masha 已经知道的号码数量和电话号码的位数。 接下来第 $n$ 行，第 $i$ 行的字符串表示已知的第 $i$ 个号码。 每组数据最后一行字符串 $s$，表示她新朋友的电话号码。 在给出的 $n+1$ 个号码中，可能存在相同的号码。 数据保证每组数据 $n\cdot m$ 的和不超过 $10^6$。 **【输出格式】** 你需要输出 $t$ 组数据的结果。每组第一行包含一个整数 $k$，表示你分割的段数。如果无解，则输出 $-1$。 如果存在解，则在输出 $k$ 之后输出 $3$ 个整数 $l,r,i$，表示分解后 $s$ 的其中的一段就是第 $i$ 个电话号码 $[l,r]$ 的子串。注意你需要保证 $k$ 行中所有 $r-l+1\ge 2$。

题目描述

Masha meets a new friend and learns his phone number — $ s $ . She wants to remember it as soon as possible. The phone number — is a string of length $ m $ that consists of digits from $ 0 $ to $ 9 $ . The phone number may start with 0. Masha already knows $ n $ phone numbers (all numbers have the same length $ m $ ). It will be easier for her to remember a new number if the $ s $ is represented as segments of numbers she already knows. Each such segment must be of length at least $ 2 $ , otherwise there will be too many segments and Masha will get confused. For example, Masha needs to remember the number: $ s = $ '12345678' and she already knows $ n = 4 $ numbers: '12340219', '20215601', '56782022', '12300678'. You can represent $ s $ as a $ 3 $ segment: '1234' of number one, '56' of number two, and '78' of number three. There are other ways to represent $ s $ . Masha asks you for help, she asks you to break the string $ s $ into segments of length $ 2 $ or more of the numbers she already knows. If there are several possible answers, print any of them.

输入输出格式

输入格式

The first line of input data contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) —the number of test cases. Before each test case there is a blank line. Then there is a line containing integers $ n $ and $ m $ ( $ 1 \le n, m \le 10^3 $ ) —the number of phone numbers that Masha knows and the number of digits in each phone number. Then follow $ n $ line, $ i $ -th of which describes the $ i $ -th number that Masha knows. The next line contains the phone number of her new friend $ s $ . Among the given $ n+1 $ phones, there may be duplicates (identical phones). It is guaranteed that the sum of $ n \cdot m $ ( $ n $ multiplied by $ m $ ) values over all input test cases does not exceed $ 10^6 $ .

输出格式

You need to print the answers to $ t $ test cases. The first line of the answer should contain one number $ k $ , corresponding to the number of segments into which you split the phone number $ s $ . Print -1 if you cannot get such a split. If the answer is yes, then follow $ k $ lines containing triples of numbers $ l, r, i $ . Such triplets mean that the next $ r-l+1 $ digits of number $ s $ are equal to a segment (substring) with boundaries $ [l, r] $ of the phone under number $ i $ . Both the phones and the digits in them are numbered from $ 1 $ . Note that $ r-l+1 \ge 2 $ for all $ k $ lines.

输入输出样例

输入样例 #1

5

4 8
12340219
20215601
56782022
12300678
12345678

2 3
134
126
123

1 4
1210
1221

4 3
251
064
859
957
054

4 7
7968636
9486033
4614224
5454197
9482268

输出样例 #1

3
1 4 1
5 6 2
3 4 3
-1
2
1 2 1
2 3 1
-1
3
1 3 2
5 6 3
3 4 1

说明

The example from the statement. In the second case, it is impossible to represent by segments of known numbers of length 2 or more. In the third case, you can get the segments '12' and '21' from the first phone number.