F. Issam's Escape Plan
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abu Ghalib locked Abu Issam in his Barbour and clinic shop using a lock with a secret $$$n$$$-digit code. We know the code is a number $$$x$$$.

When you buy these types of locks, they come with two things: the $$$n$$$-digit passcode $$$x$$$ and a hint. The hint is given in the form of two $$$n$$$-digit numbers, $$$L$$$ and $$$R$$$, where $$$(L \leq x \leq R)$$$, indicating that the passcode is between $$$L$$$ and $$$R$$$ inclusive.

Usually, people memorize the value of $$$x$$$ and then erase it to safely use the lock. However, Abu Ghalib was lazy, and he might have left some digits of $$$x$$$ visible on the lock.

Now, Abu Issam can see some $$$n$$$-digit patterns representing $$$L$$$, $$$R$$$, and $$$x$$$. In the pattern for $$$x$$$, some positions show a digit $$$(0\text{-}9)$$$, while other positions show a question mark $$$?$$$, indicating an unknown digit.

Let $$$S$$$ be the set of all possible $$$n$$$-digit codes that match the visible pattern on the lock (by replacing each $$$?$$$ with a digit) and fall within the inclusive range from $$$L$$$ to $$$R$$$. Abu Issam must open the lock before Shabab Al7ara discovers that he sleeps in the store. He has only one attempt and decides to use his lucky number $$$k$$$.

He will try the $$$k_{th}$$$ smallest number in the set $$$S$$$. If the set $$$S$$$ contains fewer than $$$k$$$ numbers, then the $$$k_{th}$$$ smallest number does not exist, and Abu Issam will be caught. In this case, print $$$-1$$$.

Input

The first line of input contains one integer $$$T$$$, representing the number of test cases $$$(1 \leq T \leq 10^5)$$$.

For each test case:

The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 18)$$$ and $$$k$$$ $$$(1 \le k \le 10^{18})$$$, denoting the number of digits in $$$x$$$, $$$L$$$, and $$$R$$$, and the lucky number respectively.

The second line contains a string $$$x$$$, consisting of digits $$$(0-9)$$$ and question marks $$$(?)$$$, where $$$?$$$ indicates an unknown digit.

The third and fourth lines each contain strings $$$L$$$ and $$$R$$$ respectively, indicating the inclusive range $$$(L \le x \le R)$$$ within which the password must lie.

Output

For each test case, find the $$$k_{th}$$$ smallest n-digit number (it can have leading zeroes) in the set $$$S$$$. If the set $$$S$$$ contains fewer than $$$k$$$ numbers, the $$$k_{th}$$$ smallest doesn't exist; in this case, print $$$-1$$$.

Example
Input
3
5 6
?78?2
51782
63451
18 3948349
??????????????????
000000000000000000
999999999999999999
3 2
123
100
200
Output
57852
000000000003948348
-1