AB String

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Given a string $S$ contains only $A$ and $B$.

Calculate the Kth string $T$ which doesn't appear in $S$.

Compare the string in order of length,if length is same,then sort in order of lexicographical order.

Input

First line contains a single integer $cases (cases \leq 5)$ which denotes the number of test cases.

For each test case, the first line is string $S (1 \leq |S| \leq 20000)$, the second line have $T+1$ numbers,the first number is $T$,next $T$ number(s) is Kth. $(1 \leq T \leq 10, 1 \leq K \leq 10^9)$

Output

For each case, output $T$ lines.

Sample Input

2 A 1 1 AAABBA 1 1

Sample Output

B ABA

Hint

hujie

Source

BestCoder Round #54 (div.1) ($)

提交代码