题目描述

请你构造 $n$ 个正整数 $a_1\sim a_n$ 满足：

• $\forall X\in [L,R]$ 且 $X$ 是偶数，$\exists b_1\sim b_n$，使得 $\forall 1\le i\le n,b_i\in \{-1,1\}$ 且 $\sum _{1\le i\le n} a_ib_i=X$。$L,R$ 的值见数据范围。
• 设 $cnt_i$ 为满足 $a_j=i$ 的 $j$ 的个数，则 $cnt_i$ 要么等于 $0$，要么大于等于 $2$。
• $1\le n\le 40$。

为了验证你的 $a_i$ 确实满足条件，会给出 $Q$ 组询问，每次询问偶数 $X \in [L,R]$，请你输出一组合法的 $b_i$。

输入格式

第一行两个正整数 $M,Q$，$M$ 表示 $X$ 的上界。在测试数据中，保证 $M=10^9$。

接下来 $Q$ 行，每行一个正偶数 $X$。保证 $X\in [L,R]$。

注意 $L,R$ 并不会在输入中给出，你可以认为 $L=\min X,R=\max X$。

输出格式

第一行输出你构造的正整数个数 $n$。$(1\le n\le 40)$

接下来一行 $n$ 个正整数 $a_1\sim a_n$。$(1\le a_i\le 10^9)$

接下来 $Q$ 行，每行 $n$ 个字符，每个字符是 + 或 -。设第 $i$ 个字符为 $s_i$，设本次询问的值为 $X$，则需要满足 $\sum _{1\le i\le n} a_i([s_i=$ + $]-[s_i=$ - $])=X$，其中 $[P]$ 在 $P$ 成立时等于 $1$，否则等于 $0$。

你输出的 $a_i$ 需要满足题面中的要求。

6 3
2
4
6

8
1 1 1 1 1 1 1 1
++-+-++-
++-++++-
++-+++++

提示

本题有三个子任务。

所有数据均满足：$2\le M\le 10^9$，$1\le Q\le 10^5$，$X\in [L,R]$。

• 子任务 $1$（$25$ 分）：$L=2$，$R=2\times 10^5$。
• 子任务 $2$（$5$ 分）：$L=10^9-2\times 10^5+2$，$R=10^9$。
• 子任务 $3$（$70$ 分）：$L=2$，$R=M$。