P5678 [GZOI2017] River God

GZOI2017 D2T1. Finally unable to endure the hard brick-carrying life of Worker X, Shlw threw the brick in his hand into the river. As expected, the River God appeared. Shlw said: “I dropped a gold brick. Give me the gold brick now!” “!!! You already know the trick?” said the River God. “But if you want the gold brick, then I won’t give you the resources for the 2017 *My Little Pony* movie. If you tell the truth, I can still consider it.” Shlw realized this was not simple. Faced with money and faith, it was hard to choose. Suddenly, Shlw ignored the River God and ran away on his own. “Sigh, young people these days... I really don’t know what they are thinking.” Pinkie Pie sighed and took off the River God disguise.

From the choices given by the River God, Shlw got inspiration for an algebra problem that he failed back then. But now he hopes you can help solve it, because he is busy searching for pony resources. Given the recurrence relations of sequences $\{a_n\}$, $\{b_n\}$, and $\{A_n\}$, find the $N$-th term of the sequence $\{A_n\}$. The recurrence is: $$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}$$ Here, $\otimes$ denotes the AND operation, and $\oplus$ denotes the OR operation.

The first line contains two positive integers $N$ and $K$. The second line contains $K$ non-negative integers separated by spaces, representing $\{a_n\}$. The third line contains $K$ non-negative integers separated by spaces, representing $\{b_n\}$.

One line with one integer, representing $\{A_n\}$.

【Sample Explanation】 From $A_0$ to $A_{10}$, they are respectively: $2, 3, 5, 7, 12, 15, 15, 13, 15, 15, 15$. 【Constraints】  【Postscript】 Later, Pinkie Pie secretly came to Shlw’s home. She took this problem back to test Apple Jack, so Apple Jack gained the ability to travel the multiverse by eating apples like crazy. Translated by ChatGPT 5