跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#LGP7814. 「小窝 R3」心の記憶

「小窝 R3」心の記憶

「小窝 R3」心の記憶

题目描述

本题中,子串必须由原字符串中连续的字符组成;子序列由原字符串中按原先顺序选出的字符组成,所选字符可以不连续。

现有 TT 次询问。每次给定一个长度为 nn 的 01 串 AA,你需要构造一个字符串 BB,使其满足:

  • BB 是长度为 mm 的 01 串。
  • BB 中不存在任何一个与 AA 相同的子串。
  • BB 中存在至少一个与 AA 相同的子序列。

输出任意一个满足要求的 BB 即可。如果不存在合法方案,输出 -1。

输入格式

第一行输入一个正整数 TT,表示询问次数。

每次询问第一行输入两个正整数 n,mn,m,满足 1≤n≤m1\leq n\leq m。第二行输入一个长度为 nn 的 01 串 AA。

对于一个输入文件中的全部询问,保证 1≤∑m≤2×1061\leq\sum m\leq2\times10^6。

输出格式

共输出 TT 行。对于每次询问,输出一个长度为 mm 的合法 01 串;如果无解,输出 -1。

样例 1

4
1 1
1
3 5
010
4 8
1101
5 6
11111
-1
01110
10100101
111101

来源

原题。题意按原题整理,测试数据由本站独立构造。