There are two strings A and B. Initially, some strings A’ and B’ are written on the sheet of paper. A’ is always a substring of A and B’ is always a substring of B. A move consists of appending a letter to exactly one of these strings: either to A’ or to B’. After the move the constraint of A’ being a substring of A and B’ is a substring of B should still be satisfied. Players take their moves alternately. We call a pair (A’, B’) a position.
Two players are playing this game optimally. That means that if a player has a move that leads to his/her victory, he/she will definitely use this move. If a player is unable to make a move, he loses.
Alice and Bob are playing this game. Alice makes the first move. As always, she wants to win and this time she does a clever trick. She wants the starting position to be the Kth lexicographically winning position for the first player (i.e. her). Consider two positions (A’1, B’1) and (A’2, B’2). We consider the first position lexicographically smaller than the second if A1 is lexicographically smaller than A2, or if A1 is equal to A2 and B1 is lexicographically smaller than B2.
What will be such a position, knowing the strings A, B and the integer K.
Note : Some of these strings can be empty. If there’s no such pair, we need to tell that their is “no solution” .
EXAMPLE : Length of A=2 , Length of B=2 and say K=5 .The strings be
ab
cd
Here answer will be :
a
cd
