Problem G
The Power of Substitution
A substitution cipher uses a substitution table that for each letter $x$ in the alphabet assigns another (possibly the same) letter $p[x]$ in the same alphabet. A message $m_1\, m_2\, m_3\, m_4$ is then encrypted as $E_ p(m_1\, m_2\, m_3\, m_4)=p[m_1]\, p[m_2]\, p[m_3]\, p[m_4]$. This only works if $p$ is one-to-one. That is, $p$ has the property that $p[x] = p[x’]$ only if $x=x’$.
Now consider the idea of iterating this, i.e., to encrypt the encryption by applying the substitution table again. We can therefore define substitution to the power $k$, denoted $E^ k_ p()$ by
\begin{eqnarray*} E^0_ p(m_1\ldots m_\ell ) & = & m_1\ldots m_\ell \\ E^{k+1}_ p(m_1\ldots m_\ell ) & = & E_ p(E^ k_ p(m_1\ldots m_\ell )) \end{eqnarray*}Now, given $m_1\ldots m_\ell $, $c_1\ldots c_\ell $, and $p[]$, we might ask (and we will!) for a $k$ such that $E_ p^ k(m_1\ldots m_\ell ) = c_1\ldots c_\ell $.
In our case the alphabet will have $100$ symbols denoted $1, 2,\ldots , 100$. You will be given a message, $m$, a cryptotext, $c$, and a substitution table, $p$. You are to find a $k$ such that $E^ k_ p(c)=d$. Specifically, we want such a $k$ in the interval $0\leq k\leq 10^9$ (there will always be a solution for the test cases).
Input
The input starts with an integer $1 \le N \le 20$ on a line by itself. This is the number of test cases.
A test case consists of four lines: first a single integer $L$ which is the size of the message (at least $1$, at most $200$), second a line with $L$ numbers (the message $m$), third a line with $L$ numbers (the crypto text $c$) and finally a line with $100$ numbers giving the substitution table $p[]$ (the first number is $p[1]$, the second is $p[2]$ and so on).
You can assume that the numbers in the message and crypto text are all integers that are at least $1$ and at most $100$. You can assume the same for $p$, and furthermore that $p$ is one-to-one.
Output
For each test case output a single integer $k$ on a line by itself. This $k$ should be non-negative and at most $10^9$, and obviously satisfy $E^ k_ p(m)=c$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 1 2 3 4 5 6 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 3 1 2 9 2 1 10 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 39 42 41 44 43 46 45 48 47 50 49 52 51 54 53 56 55 58 57 60 59 62 61 64 63 66 65 68 67 70 69 72 71 74 73 76 75 78 77 80 79 82 81 84 83 86 85 88 87 90 89 92 91 94 93 96 95 98 97 100 99 |
3 1 |
