You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在密码学中，代换-置换网络（或译作置换排列网络，英语：Substitution-Permutation Network，缩写作 SP-network 或 SPN）是乘积密码和分组加密的一种，美国数学家克劳德·香农在1949年为了找到利用简单的代换-置换方式进行加密的安全加密方式，发明了代换-置换网络。本题希望你实现代换-置换网络加密，对输入的明文字符串进行代换-置换加密并打印输出。

代换-置换网络

代换-置换网络包括两个变换，分别记为 $π_s 和 π_p$。

$\pi_s : \{0,1\}^l \rightarrow \{0,1\}^l$

$\pi_p : \{1,lm\} \rightarrow \{1,lm\}$

都是置换，置换 $\pi_s$ 叫做S盒，它用一个 lBit向量来替代另一个 lBit向量

换 $\pi_p$ 用来置换lm个Bit

给定一个lmBit的二元串 $x = (x_1,\ldots,x_{lm})$，可以将其看做m个lBit字串 $x_1,\ldots,x_m$的并联

因此 $x = x_1||\ldots||x_m$，且对于 $1\leq i \leq m$ ，我们有 $x = (x_{(i-1)l+1},\ldots,x_{il})$

下面给出的代换-置换网络由Nr轮组成，在每一轮我们先用异或操作混入该密钥，再用$\pi_s$进行m次代换，然后用$\pi_p$进行一次置换

密码体制：设l,m和Nr都是正整数， $\pi_s : \{0,1\}^l \rightarrow \{0,1\}^l 与 \pi_p : \{0,lm\} \rightarrow \{0,lm\}$均为置换

设 $P=C={0,1}，K \in ({0,1}^{lm})^{N_{r+1}}$ 是由初始密钥K用密钥编排算法生成的所有可能密钥编排方案之集

对一个密钥编排方案 $K^1,\ldots,K^{N_{r+1}}$，我们可以用下面的算法加密明文x

注意：⊕ 的意思是异或，上面S盒的代换是分组代换，也就是10进制数字变成二进制，每组四个位置。

下面用一个特定的代换-置换网络来说明上面的一般性描述

设$l=m=N_r=4,\pi_s$如下定义，这里输入 z 和输出 $\pi_s(z)$都以十六进制表示$（0 \leftrightarrow (0,0,0,0),1\leftrightarrow(0,0,0,1),\ldots,9\leftrightarrow(1,0,0,1),A\leftrightarrow(1,0,1,0),\ldots,F\leftrightarrow(1,1,1,1)）$

$\pi_{s(z)}$如下定义

$\pi_{p(z)}$如下定义

为了叙述方便，我们命名了16个 S 盒，$S^i_r(1 \geq i \geq 4,1 \geq \geq 4)$，它们都是基于同样的置换$π_s$。下面给出代换-置换网络的密钥编排算法。我们以一个32比特的密钥 $K=(k_1,...,k_32)∈{0,1}^32$ 开始。对轮数$1\leq r \leq 5$，定义$K^r$是由$K$中从$k_{4r−3}$开始的16个相邻比特组成的。

下面我使用该代换-置换网络来进行加密。所有的数据都用二元形式表示。

设密钥是：

$K=0011 1010 1001 0100 1101 0110 0011 1111$

则轮密钥如下：

$K1=0011 1010 1001 0100$

$K2=1010 1001 0100 1101$

$K3=1001 0100 1101 0110$

$K4=0100 1101 0110 0011$

$K5=1101 0110 0011 1111$

设明文为：

$x=0010 0110 1011 0111$

则加密$x$的过程如下：

密文为：

$y = 1011 1100 1101 0110$

具体解释一下上面比较难以理解的由$u$到$v$的过程，这里分为四组，每组四个数字，分为四次进行$S$盒代换，一共代换16位，代换后的十进制数字再转成二进制数字填入$v$数组。

数据范围

• $0 \leq z，\pi_s(z) \leq 15，\pi_s(z)中A由10表示，B由11表示以此类推$

• $1 \leq z，\pi_s(z) \leq 16$

• 密钥K为32位二进制

• 需要加密的明文为16位二进制

输入

第一行和第二行输入各输入16个数字表示$\pi_s$盒置换

第三行和第四行输入各输入16个数字表示$\pi_p$盒置换

第五行输入密钥

第六行输入明文

输出

输出明文通过SPN加密后的结果

样例

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16
0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1

1011110011010110

12 1 9 2 0 11 7 3 4 15 8 5 14 13 10 6
11 14 7 15 3 4 8 6 10 1 5 0 13 9 12 2
13 2 10 3 1 12 8 4 5 16 9 6 15 14 11 7
12 15 8 16 4 5 9 7 11 2 6 1 14 10 13 3
1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0
0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1

0010001100011101

样例解释

样例一就是上面举得例子