G-小红的字符串构造（hard）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题为问题的困难版本，两题的唯一区别在本题不保证给出数组中的「01串」两两有前缀关系。

$\hspace{15pt}$ 我们称一个字符串为「01串」，当且仅当其中仅含有字符 $\texttt{0}$ 和 $\texttt{1}$ 。

$\hspace{15pt}$ 小红拿到了长为 $n$ 的「01串」数组 $s$ 。现在她想要构造一个字符串 $s '$ ，满足 $s$ 中恰好有 $k$ 个「01串」（可以相同）是 $s'$ 的前缀。请你帮帮她。

【名词解释】
$\hspace{15pt}$ 前缀：从字符串开头到任意位置的子串。如对于字符串 $\texttt{1234}$ ，他的前缀有 $\texttt{1},\texttt{12},\texttt{123},\texttt{1234}$ 和空串。

第一行输入两个整数 。之后的  行，每行输入一个非空「01串」 。

除此之外，保证单个测试文件的  之和不超过 。

如果不存在合法的字符串，请输出 ；否则请输出所构造的字符串 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

复制

复制

，， 是  的前缀。