Problem Description

Please construct $n$ positive integers $a_1 \sim a_n$ that satisfy:

• For every even $X \in [L,R]$, there exist $b_1 \sim b_n$ such that for all $1 \le i \le n$, $b_i \in \{-1,1\}$ and $\sum_{1 \le i \le n} a_i b_i = X$. The values of $L$ and $R$ are given in the Constraints.
• Let $cnt_i$ be the number of indices $j$ such that $a_j = i$. Then $cnt_i$ must be either $0$ or at least $2$.
• $1 \le n \le 40$.

To verify that your $a_i$ indeed satisfy the conditions, $Q$ queries will be given. In each query, an even $X \in [L,R]$ is given. You need to output one valid set of $b_i$.

Input Format

The first line contains two positive integers $M, Q$, where $M$ is the upper bound of $X$. In the testdata, it is guaranteed that $M = 10^9$.

In the next $Q$ lines, each line contains one positive even integer $X$. It is guaranteed that $X \in [L,R]$.

Note that $L$ and $R$ are not given in the input. You may assume that $L = \min X$ and $R = \max X$.

Output Format

The first line outputs the number of positive integers you construct, $n$. $(1 \le n \le 40)$.

The next line outputs $n$ positive integers $a_1 \sim a_n$. $(1 \le a_i \le 10^9)$.

In the next $Q$ lines, each line contains $n$ characters, each being + or -. Let the $i$-th character be $s_i$, and let the value in this query be $X$. Then it must satisfy $\sum_{1 \le i \le n} a_i([s_i=$ + $]-[s_i=$ - $]) = X$, where $[P]$ equals $1$ if $P$ is true, and $0$ otherwise.

The $a_i$ you output must satisfy the requirements in the statement.

Input Format

The first line contains two positive integers $M, Q$, where $M$ is the upper bound of $X$. In the testdata, it is guaranteed that $M = 10^9$.

In the next $Q$ lines, each line contains one positive even integer $X$. It is guaranteed that $X \in [L,R]$.

Note that $L$ and $R$ are not given in the input. You may assume that $L = \min X$ and $R = \max X$.

Output Format

The first line outputs the number of positive integers you construct, $n$. $(1 \le n \le 40)$.

The next line outputs $n$ positive integers $a_1 \sim a_n$. $(1 \le a_i \le 10^9)$.

In the next $Q$ lines, each line contains $n$ characters, each being + or -. Let the $i$-th character be $s_i$, and let the value in this query be $X$. Then it must satisfy $\sum_{1 \le i \le n} a_i([s_i=$ + $]-[s_i=$ - $]) = X$, where $[P]$ equals $1$ if $P$ is true, and $0$ otherwise.

The $a_i$ you output must satisfy the requirements in the statement.

6 3
2
4
6

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

Hint

This problem has three subtasks.

All testdata satisfy: $2 \le M \le 10^9$, $1 \le Q \le 10^5$, $X \in [L,R]$.

• Subtask $1$ ($25$ points): $L = 2$, $R = 2 \times 10^5$.
• Subtask $2$ ($5$ points): $L = 10^9 - 2 \times 10^5 + 2$, $R = 10^9$.
• Subtask $3$ ($70$ points): $L = 2$, $R = M$.

Translated by ChatGPT 5