提醒：以下题目描述中不涉及任何剧透，拒绝炎上

阿库亚和露比参加了一档综艺节目，在节目上，露比给出了一个幸运数字 $k$，同时阿库亚根据露比给出的幸运数字 $k$ 写了一个幸运 $01$ 串 $s$（由字符0和字符1组成的字符串）。

当一个 $01$ 串 $s$ 是幸运的，当且仅当所有长度为 $k$ 的 $01$ 串皆为 $s$ 的子序列（不要求连续），例如幸运数字 $k=3$，那么 $01$ 串 $00101101$ 便是幸运的，因为它的子序列集合中包含了所有长度为 $3$ 的 $01$ 串：$000、001、010、011、100、101、110、111$。

但是综艺主持人使坏，他擦去了阿库亚写下的幸运 $01$ 串的一部分，让剩下的部分组成了一个新串，并询问阿库亚：

至少需要在新串的末尾添加多少个 $0$ 或 $1$，才能使它再次成为幸运 $01$ 串？

第一行两个正整数 $n,k(1\leq n,k\leq 10^{6})$，表示新串长度 $n$ 和幸运数字 $k$。

第二行一个由 $0$ 和 $1$ 组成的 $01$串，长度为 $n$，表示主持人给出的新串。

一行一个非负整数，表示至少需要添加的 $0$ 或 $1$ 的个数。

样例的一种方案是在末尾添加 $01$，变成 $0010101$，这样其子序列集合便包含了所有长度为 $3$ 的 $01$ 串：$000、001、010、011、100、101、110、111$。
子序列的定义为：某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。