题目描述

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 认识了一个新朋友并且获得了他的电话号码 $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$。