Fox Ciel下车后,发现自己坐错了车,在陌生的小镇迷了路。然而幸运的是,她遇到了她的朋友海狸太郎,并询问去她的城堡走哪条路。太郎给她的回应是字符串s,她尝试着正确地记住字符串s。
然而,Ciel 觉得 n 个字符串 b1, b2, ... , bn 真的很无聊,不幸的是她不喜欢记住一个包含无聊子串的字符串。更糟糕的是,她能记住的只是 s 的连续子串。
确定 s 中不包含任何无聊字符串的最长连续子串,以便她能够记住太郎响应中最长的部分。
输入
第一行有一个字符串 s。 s 的长度将在 1 到 105 之间(包含 1 和 105)。
第二行有一个整数 n (1 ≤ n ≤ 10)。 接下来的 n 行,有一个字符串 bi (1 ≤ i ≤ n)。 bi 的每个长度将在 1 到 10 之间(包含 1 和 10)。
给定字符串的每个字符将是英文字母(小写和大写)或下划线('_')或数字。假设这些字符串区分大小写。
输出
在第一行输出两个空格分隔的整数 len 和 pos:s 中不包含任何 bi 的最长连续子串的长度,以及子串的第一个位置(从 0 开始索引)。位置 pos 必须介于 0 和 |s| 之间- len 包含在内,其中 |s|是字符串 s 的长度。
如果有多个解,则输出任意一个。
示例
输入 #1
Go_straight_along_this_street 5 str long tree biginteger ellipse
输出 #1
12 4
输入 #2
IhaveNoIdea 9 I h a v e N o I d
输出 #2
0 0
输入 #3
unagioisii 2 ioi unagi
输出 #3
5 5
注意
在第一个示例中,解为 traight_alon。
在第二个示例中,解决方案是空字符串,因此输出可以是“0 0”、“0 1”、“0 2”等。
在第三个示例中,解决方案是 nagio 或 oisii。