题目描述

给定一个字符串，只包含大写字母，求在包含同一字母的子串中，长度第 $k$ 长的子串的长度。相同字母只取最长的那个子串（即对每个字母，仅考虑其最长的连续出现长度）。

输入描述

第一行有一个字符串（$1 <$ 长度 $\leq 100000$），只包含大写字母。
第二行为 $k$ 的值。

输出描述

输出连续出现次数第 $k$ 多的字母的次数。当第 $k$ 多的次数不存在时，请输出 $-1$。

样例

输入

AAAAHHHBBCDHHHH
3

输出

2

说明

• 字母 A 的最长连续子串长度为 4。
• 字母 H 的最长连续子串长度为 4（最后的 HHHH）。
• 字母 B 的最长连续子串长度为 2。
• 字母 C 和 D 的最长连续子串长度为 1。

所有字母的最长连续长度为：[4, 4, 2, 1, 1]。去重后按降序排列为：[4, 2, 1]。

第 3 长的是 2，因此输出 2。

样例2

输入

AABAAA
2

输出

1

说明

• A 的最长连续子串长度为 3。
• B 的最长连续子串长度为 1。

所有字母的最长连续长度为：[3, 1]。去重后按降序排列为：[3, 1]。

第 2 长的是 1，因此输出 1。

样例3

输入

ABC
4

输出

-1

说明

只含有 3 个包含同一字母的子串（每个字符本身），不同字母的最长连续长度为 [1, 1, 1]，去重后为 [1]。第 4 长的不存在，因此输出 $-1$。

样例4

输入

ABC
2

输出

1

说明

三个子串长度均为 1，所以每个字母的最长连续长度为 1。去重后为 [1]。虽然只有一个唯一值，但第 1、第 2、第 3 长的都是 1（视为存在），因此当 $k=2$ 时输出 1。