Description

Shlw 从河神给的选择中, 获得了一道当年挂掉的代数题的灵感.

但现在他希望你来帮忙解答, 因为他自己忙着去搜小马资源去了.

给出数列 $\{a_n\}$ 和 $\{b_n\}$ 以及 $\{A_n\}$ 的递推关系, 试求出数列 $\{A_n\}$ 第 $N$ 项.

递推关系为:

$$A_n=\begin{cases}a_n & 0 \le n < K \\ \bigoplus_{0 \le t < K} (A_{n-K+t} \otimes b_t) & n \ge K \end{cases}$$

其中，$\otimes$ 表示与操作，$\oplus$ 表示或操作。

Input Format

第一行两个正整数 $N$ 和 $K$ 。

第二行 $K$ 个空格隔开的非负整数, 表示 $\{a_n\}$。

第三行 $K$ 个空格隔开的非负整数, 表示 $\{b_n\}$。

Output Format

一行, 一个整数, 表示$\{A_n\}$。

10 5
2 3 5 7 12
23 45 2 4 8

15

Hint

【样例解释】

从 $A_0$ 至 $A_{10}$ 分别为: $2, 3, 5, 7, 12, 15, 15, 13, 15, 15, 15$

【数据约束】

【后记】

后来, Pinkie Pie 偷偷来到 Shlw 家里, 她把这题拿回去考 Apple Jack, 于是 Apple Jack就有了狂吃苹果来畅游多重宇宙的本领.