F. Memeable String
time limit per test
7 seconds
memory limit per test
256 megabytes
input
protecting-memes.in
output
standard output

Khaled Hamed shares memes, a lot of memes, and as we all know any meme has a type represented by a lowercase Latin letter. Khaled's feed can be represented by a string S of size N where Si is the type of the ith meme he shares.

Your mission here is to rid the world of Khaled's non-funny memes. You get 2N - 1 - i IQ points for deleting the ith meme.

However, there is a string P that your teacher Pillow gave you. He told you that whatever you do S should always contain P as a subsequence.

Khaled knowing your schemes decided to protect some of his most important memes. He will present you with a binary string B such that if B[i] = 0 then you will be unable to delete the ith meme.

Can you find out the memes that should be deleted to achieve the maximum number of IQ points with P appearing in S as subsequence after the deletions?

Note that Pillow guarantees that P is initially a subsequence of S.

Input

The first line consists of a single integer T (1 ≤ T ≤ 10), denoting the number of test cases.

The first line of each test case contains two integers N and M (1 ≤ M ≤ N ≤ 2 × 105), denoting the size of S and P.

Followed by two lines containing strings S and P respectively consisting of lowercase Latin letters.

Followed by the binary string B of length N where (0 ≤ Bi ≤ 1).

Output

For each test case print a binary string ans where ansi = 1 if it's optimal to delete the ith meme.

Example
Input
2
12 6
yasserfaksan
yassan
111101010001
20 6
pileofpillsforpillow
pillow
11111111111111111111
Output
001001010000
11111111111111000000
Note

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.