题目描述

在经历了两场表现不佳的 Codeforces 轮次之后，Elena 开始怀疑自己为什么会相信自己能做信息学题，于是决定回到数学的怀抱。作为热身，她给自己出了下面这道简单题：

计算 $a_n$，其中：

• 前 $k$ 个元素分别为 $a_1,a_2,\dots,a_k$；

• 对于 $i>k$，有

  $$a_i=(m_1\times a_{i-k}+m_2\times a_{i-k+1}+\dots+m_k\times a_{i-1})\bmod 2;$$

• $x\bmod 2$ 表示 $x$ 除以 $2$ 的余数。

尽管她并不情愿，Elena 还是得检查自己的计算结果，而这用程序来做最方便。请你编写程序 calculations，对于不同的 $n,a_1,a_2,\dots,a_k$，计算对应的 $a_n$。

输入格式

第一行输入两个正整数 $T$ 和 $k$，分别表示需要解决多少组询问，以及已知多少个初始值。

第二行输入 $m_1,m_2,\dots,m_k$，即题目中递推关系里的系数。

接下来的 $T$ 行中，每行给出 $k+1$ 个数： $n,a_1,a_2,\dots,a_k$，分别表示要查询第几个元素，以及该组询问中数列的前 $k$ 项。

输出格式

对于每组询问，输出一行一个整数，表示对应的答案。

数据范围

• $1\le T\le 5\times 10^5$
• $1\le k\le 20$
• 对所有 $i=1,2,\dots,k$，有 $0\le a_i,m_i\le 1$
• $1\le n\le 10^9$

样例 #1

输入 #1

10 4
0 1 1 0
8 0 0 1 1
4 1 1 1 1
6 1 1 1 1
3 0 1 1 1
7 0 1 1 0
4 0 0 1 1
1 0 1 1 0
5 1 0 1 1
2 1 0 0 1
3 0 0 0 1

输出 #1

1
1
0
1
0
1
0
1
0
0

子任务

只有当某个子任务以及它所依赖的全部前置子任务都通过时，才会获得该子任务的分数。