Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0139 - SHUFFLING STRINGS

  Suppose S1 and S2 are two strings of size n consisting of characters A through H (capital letters). We plan to perform the following step several times to produce a given string S. In each step we shuffle S1 and S2 to get string S12. Indeed, S12 is obtained by scanning S1 and S2 from left to right and putting their characters alternatively in S12 from left to right. The shuffling operation always starts with the leftmost character of S2. After this operation, we set S1 and S2 to be the first half and the second half of S12, respectively. For instance, if S1 = ABCHAD and S2 = DEFDAC, then S12 = DAEBFCDHAACD, and for the next step S1 = DAEBFC and S2 = DHAACD. For the given string S of size 2n, the goal is to determine whether S12 = S at some step.

Input

   There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers 0 ≤ n ≤ 100 which is the length of S1 and S2. The remainder of each test case consists of three lines. The first and the second lines contain strings S1 and S2 with size n, respectively, and the last line contains string S with size 2n. The input terminates with “0” which should not be processed.

Output

   For each test case, output -1 if S is not reachable. Otherwise, output the minimum number of steps to reach S. To make your life easier, we inform you that the output is not greater than 50 for the given input.

Examples

stdin

stdout

1

4

AHAH

HAHA

HHAAAAHH

3

CDE

CDE

EEDDCC

0

2

-1


Ավելացրեց.Հրանտ Հովհաննիսյան (ԳՏՏԿ)
Ամսաթիվ.2014-02-09
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Iran Internet 2013.E

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.