P5678 [GZOI2017] 河神

GZOI2017 D2T1 终于忍受不了苦 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\}$。

【样例解释】 从 $A_0$ 至 $A_{10}$ 分别为：$2, 3, 5, 7, 12, 15, 15, 13, 15, 15, 15$。 【数据约束】 |测试点编号|$N$|$K$|其他限制| |:-:|:-:|:-:|:-:| |$1$|$\le10^4$|$\le100$|无| |$2$|$\le10^9$|$=1$|^| |$3\sim5$|$\le10^6$|$\le10$|$a_n,b_n