Tired of the grueling life of a manual laborer, Shlw threw his brick into the river.

As expected, the River God emerged.

Shlw said, "I dropped a gold brick, give me a gold brick!"

"!!! You already know the routine," the River God said, "but if you want the gold brick, I won't give you the resources for the 2017 My Little Pony movie. If you tell the truth, I might consider it."

Shlw realized things were not that simple; faced with money and faith, it was a difficult choice.

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, taking off her River God disguise.

From the choices given by the River God, Shlw found inspiration for an algebra problem he had failed to solve back in the day.

But now he wants you to help solve it, because he is busy searching for pony resources.

Given the recurrence relations for sequences $\{a_n\}$, $\{b_n\}$, and $\{A_n\}$, find the $N$-th term of the sequence $\{A_n\}$.

The recurrence relation 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}$$

Where $\otimes$ denotes the bitwise AND operation, and $\oplus$ denotes the bitwise OR operation.

Input

The first line contains two positive integers $N$ and $K$.

The second line contains $K$ space-separated non-negative integers, representing $\{a_n\}$.

The third line contains $K$ space-separated non-negative integers, representing $\{b_n\}$.

Output

A single line containing an integer, representing $A_N$.

Examples

Input 1

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

Output 1

15

Note 1

The values from $A_0$ to $A_{10}$ are: $2, 3, 5, 7, 12, 15, 15, 13, 15, 15, 15$

Subtasks

For $100\%$ of the data, $0 \leq a_n, b_n \leq 2^{63} - 1$, $1 \leq K \leq 100$, $1 \leq N \leq 10^9$.

Later, Pinkie Pie snuck into Shlw's house and took this problem back to test Apple Jack, which gave Apple Jack the ability to eat apples frantically and travel through the multiverse.