Description

众所周知，Arahc 是一种神秘生物，所以他的基因碱基不由 A,G,C,U/T 组成，而是由阴嘌呤和阳嘧啶组成，分别记作 $0,1$。

Arahc 的物种的原生质组成可以表示为一个长度为 $n$ 的 01 串 $A$，Arahc 本身的基因只知道可以表示为长为 $m$ 的 01 串 $B$，但是不知道 $B$ 的具体信息。

已知从原生质进化为 Arahc 的过程中，基因发生了大幅度的改变，导致 $B$ 中找不到任意一个和 $A$ 相同的子串，但是由于是从原生质进化的，$B$ 中至少含有一个和 $A$ 相同的子序列。

给定 $A$，你需要推测一种可能的 Arahc 的基因 $B$。若这样的基因不存在，说明 Arahc 物种的进化树 被深不可测的伟力所侵 了，输出 ?。

Format

Input

本题含有多组数据。第一行一个正整数 $T\,(1\leq T\leq 10^5)$ 表示数据组数。

对于每组数据，第一行两个正整数 $n,m\,(1\leq n,m\leq 10^5)$，分别表示 $A,B$ 的长度。

第二行一个长度为 $n$ 的 01 串 $A$，表示原生质的基因。

保证所有数据的 $n,m$ 分别的总和满足 $1\leq \sum n,\sum m\leq 10^6$.

Output

对于每组数据，输出一行一个长度为 $m$ 的 01 串 $B$ 或一个字符 ?。

Samples

3
3 6
101
2 3
01
4 6
1101

110011
?
101010

Limitation

1s, 256MiB.