题目描述

给定了两个长为 $m$ 的数列 $a_1,\dots,a_m$，$c_1,\dots,c_m$，以及一个递推关系（$k>m$ 时）：

$$a_k=\operatorname{and}_ {i=1}^{m}(a_{k-i}\operatorname{or}c_i), $$

你需要求出 $a_n$ 的值。

其中 $\operatorname{and}$ 表示按位与运算，$\operatorname{or}$ 表示按位或运算。

输入格式

第一行两个整数 $n,m$。

第二行 $m$ 个整数表示 $c_1,\dots,c_m$。

第三行 $m$ 个整数表示 $a_1,\dots,a_m$。

输出格式

一个整数表示 $a_n$ 的值。

4 2
23 7
13 20

23

说明/提示

样例解释

$a_3=(a_2\operatorname{or}c_1)\operatorname{and}(a_1\operatorname{or}c_2)=(20\operatorname{or}23)\operatorname{and}(13\operatorname{or}7)=23\operatorname{and}15=7$，

$a_4=(a_3\operatorname{or}c_1)\operatorname{and}(a_2\operatorname{or}c_2)=(7\operatorname{or}23)\operatorname{and}(20\operatorname{or}7)=23\operatorname{and}23=23$。

---

数据范围与约定

本题共有 $10$ 个测试点，每个测试点 $10$ 分。各测试点数据范围与限制如下。

Testcase No.	$n\le$	$m\le$	特殊限制
$1\sim2$	$100$		无
$3\sim4$	$300$		$n \le m$
$5\sim7$	$10^5$	$3$	无
$8\sim10$	$2\times10^{16}$	$300$

对于所有数据，$1 \le n \le 2 \times 10^{16}$，$1 \le m \le 300$，$0 \le a_i,c_i<2^{32}$。