408501: GYM103158 F Memeable String
Description
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.
InputThe 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).
OutputFor each test case print a binary string ans where ansi = 1 if it's optimal to delete the ith meme.
ExampleInput2 12 6 yasserfaksan yassan 111101010001 20 6 pileofpillsforpillow pillow 11111111111111111111Output
001001010000 11111111111111000000Note
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.