{"raw_statement":[{"iden":"background","content":"死而复生，生而复死。所谓的不死鸟就是这样的一种生物，在无尽的时间里无尽地循环往复。\n\n果然最好还是别获得不老不死的能力吧。"},{"iden":"statement","content":"不死鸟的「一生」可以被看成一个长度不超过 $l_{\\max}$ 的字符串 $S_0$。在无尽的轮回后形成了一个无限长的字符串 $S_{\\mathrm{inf}}=S_0+S_0+S_0+\\cdots$。现在截取 $S_{\\mathrm{inf}}$ 前 $l$ 个字符，作为可观测时间里不死鸟的生命 $S_{\\mathrm{fin}}$。\n\n然而所谓的轮回并不是机械死板的循环往复。因此，$S_\\mathrm{fin}$ 当中会有**不超过 $n$ 个字符**被修改成了别的字符，变成了 $S_{\\mathrm{real}}$。\n\n现在观测到了 $S_{\\mathrm{real}}$，我们希望找到这轮回的周期 $S_0$。然而由于不死鸟的轮回太过漫长，我们只希望找到这样一个 $S_0'$，使得由它生成的 $S_\\mathrm{fin}'$ 修改**不超过 $m$ 个字符**后就可以变成 $S_{\\mathrm{real}}$。\n"},{"iden":"input","content":"第一行有四个正整数 $l,l_{\\max},n,m$。\n\n第二行描述观测到的长度为 $l$ 的字符串 $S_{\\mathrm{real}}$。"},{"iden":"output","content":"第一行输出一个正整数 $l_0$，表示你所找到的 $S_0$ 的长度。你应当保证 $1\\le l_0\\le l_{\\max}$。\n\n第二行输出一个长度为 $l_0$ 的字符串 $S_0$，表示你所找到的字符串。"},{"iden":"note","content":"### 样例解释\n\n样例仅供理解题意，**不符合数据范围的约束**。具体约束请参见「数据范围及约定」。\n\n生成 $S_{\\mathrm{real}}$ 所用的 $S_0=\\verb!aabcd!$。\n\n- 由此生成 $S_{\\mathrm{inf}}=\\verb!aabcdaabcdaabcdaabcdaabcd!\\cdots$；\n- 由此生成 $S_{\\mathrm{fin}}=\\verb!aabcdaabcdaabcdaabcdaabcd!$；\n- 由此生成 $S_{\\mathrm{real}\\kern{-2.5pt}}=\\verb!aaacdaabbbaabccaabcdaabcd!$。\n\n样例输出给出了一个可能的 $S_0'=\\verb!aaacd!$。由此计算出 $S_{\\mathrm{fin}}'$ 与 $S_{\\mathrm{real}}$ 的差距：\n\n$$\\begin{aligned}\nS_{\\mathrm{fin}}'=&\\texttt{aaacdaa\\textcolor{red}a\\textcolor{red}c\\textcolor{red}daa\\textcolor{red}ac\\textcolor{red}daa\\textcolor{red}acdaa\\textcolor{red}acd}\\cr\nS_{\\mathrm{real}}=&\\texttt{aaacdaabbbaabccaabcdaabcd}\\cr\n\\end{aligned}$$\n\n相差为 $7$，不超过 $m=10$，可以被接受。\n\n### 数据范围及约定\n\n对于全部数据，保证 $l=3\\times 10^5$，$n=3\\times 10^3$，$m=10^4$，$1\\le l_{\\max} \\le 10^5$。"}],"translated_statement":null,"sample_group":[["25 8 5 10\naaacdaabbbaabccaabcdaabcd\n","5\naaacd"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}