终于忍受不了苦 X 的搬砖生活, Shlw 把手里的板砖扔进了河里.
不出意料地, 河神冒了出来.
Shlw 说: “我掉了金砖, 快给我金砖!”
“!!! 你已经知道套路了吗,”河神说道, “但是你要金砖的话, 我就不给你2017 彩虹小马大电影的资源了哦. 如果你说实话的话, 我还可以考虑一下.”
Shlw 发现事情并不简单, 在金钱和信仰面前, 难以抉择.
突然, Shlw 不理会河神, 自顾自的地跑走了.
“唉, 现在的年轻人啊... 真不知道在想什么.”Pinkie Pie 感叹, 卸下了河神伪装.
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$ 表示或操作。
输入格式
第一行两个正整数 $N$ 和 $K$ 。
第二行 $K$ 个空格隔开的非负整数, 表示 $\{a_n\}$。
第三行 $K$ 个空格隔开的非负整数, 表示 $\{b_n\}$。
输出格式
一行, 一个整数, 表示$\{A_n\}$。
样例数据
样例输入
10 5 2 3 5 7 12 23 45 2 4 8
样例输出
15
样例解释
从 $A_0$ 至 $A_{10}$ 分别为: $2, 3, 5, 7, 12, 15, 15, 13, 15, 15, 15$
子任务
对于 $100\%$ 的数据，$0 \leq a_n, b_n \leq 2^{63} - 1$，$1 \leq K \leq 100$，$1 \leq N \leq 10^9$
| 测试点编号 | $N$ | $K$ | 其他限制 |
|---|---|---|---|
| $1$ | $\leq 10^4$ | $\leq 100$ | 无 |
| $2$ | $\leq 10^9$ | $= 1$ | |
| $3 \sim 5$ | $\leq 10^6$ | $\leq 10$ | $a_n, b_n < 2$ |
| $6 \sim 7$ | $\leq 10^8$ | $\leq15$ | 无 |
| $8 \sim 10$ | $\leq 10^9$ | $\leq100$ |
后来, Pinkie Pie 偷偷来到 Shlw 家里, 她把这题拿回去考 Apple Jack, 于是 Apple Jack就有了狂吃苹果来畅游多重宇宙的本领.