Recurrence with Bitwise Operations

Given two sequences ({a_n}) and ({b_n}), and a sequence ({A_n}) defined by the recurrence

[ A_n = \begin{cases} a_n, & 0 \le n < K, \ \displaystyle \bigoplus_{t=0}^{K-1} \Bigl( A_{n-K+t} \otimes b_t \Bigr), & n \ge K, \end{cases} ]

where (\otimes) denotes the bitwise AND operation and (\oplus) denotes the bitwise OR operation. Your task is to compute the (N)th term of the sequence, i.e. output (A_N).

inputFormat

The first line contains two integers (K) and (N). The second line contains (K) space-separated integers representing (a_0, a_1, \ldots, a_{K-1}). The third line contains (K) space-separated integers representing (b_0, b_1, \ldots, b_{K-1}).

outputFormat

Output a single integer, the value of (A_N).

sample

3 4
1 2 3
1 0 1

1