Description

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.

Input Format

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\}$.

Output Format

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

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

15

Hint

【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