U211078 [小翔系列水题] 蒜头

小翔在大师的帮助下，终于发现了蒜头窝。 这时，他就要练习切割，剥皮和合并的魔法了！

给定 $n$ 颗蒜头。每颗蒜头有两个特征值： $a$ 和 $b$ 。第 $i$ 颗蒜头的特征值分别记为 $a_i$ 和 $b_i$ 。现在有一个正整数常数 $p$ 。 现在，小翔要能进行以下操作： * 合并从左往右数第 $i$ 个和第 $i+1$ 个蒜头，使新蒜头的 $a$ 变为 $a_i\times a_{i+1}\mod p$ 。 * 对从左往右数第 $i$ 个蒜头进行切割，使 $a_i$ 变为 $\lfloor\frac{a_i}{2}\rfloor$ ，并产生一个特征值 $a$ 为 $\lfloor\frac{a_i}{2}\rfloor$ 的蒜头紧贴在第 $i$ 个蒜头右边。 * 对从左往右数第 $i$ 个蒜头进行剥皮。剥皮完 $a_i$ 变为 $b_i$ 。 小翔的操作有以下限制： * 进行操作的蒜头必须**存在**，即不能将蒜头与空气合并，也不能将空气和空气合并，也不能将空气剥皮、切割。 * **新产生的**蒜头和**进行过任何操作的**蒜头**都不能再切割或者剥皮**。 * 最多进行 $m$ 次切割操作和 $k$ 次剥皮操作。 * 最终一定要合成一个蒜头。 请求出最后合成的蒜头的特征值 $a$ 的最大值是多少。

第一行四个非负整数 $n,m,k,p$ 。 第二行 $n$ 个正整数，表示 $a_i$ 。 第三行 $n$ 个正整数，表示 $b_i$ 。

输出一行一个非负整数，表示最终答案。

### 样例解释 把第 $5$ 个蒜头切割，把第 $4$ 个蒜头剥皮。 接下来按 $2,1,4,3,5,6$ 的顺序依次合并。 答案为： $4\times 2\times 4\times 6\times 2\times 2\mod 10 = 8$ 可以证明没有更优解。 ### 数据范围 对于 $20\%$ 的数据，所有输入数据小于等于 $28$ 。 对于 $40\%$ 的数据，所有输入数据小于等于 $68$ 。 对于另外 $20\%$ 的数据，有 $k=0$ 。 对于 $100\%$ 的数据，有 $1\leq n\leq 500,0\leq m\leq 50,0\leq k\leq n,2\leq p\leq 288,0\leq a_i,b_i