曾经，s1mple 找到了著名的解题专家 Kostya，并说道： “如果你想变得更强，你需要不断的练习。这里有一道训练题：”
给定一个大小为 $n \times m$ 的矩阵 $a$（$n$ 表示行数，$m$ 表示列数），其中每个元素要么是 $0$ 要么是 $1$。已知每列恰好包含 $c_i$ 个 $1$。每一列中的元素可以任意排列。目标是最大化含有奇数个 $1$ 的行数，并构造出这样一个矩阵。
Kostya 默默地点了点头，在桌前坐下，开始工作，他深知每一次练习都让他离大师更近一步。
Kostya 没能解决这个问题，请求你帮他解决。
如果你只求出数量而不输出矩阵，也可以获得部分分数。详情见下文。
输入格式
第一行包含两个整数 $n$ 和 $m$ ($1 \le n \cdot m \le 10^6$) — 矩阵的维度。
第二行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$ ($0 \le c_i \le n$) — 每列中 $1$ 的个数。
输出格式
第一行输出一个整数 $t$ ($0 \le t \le n$) — 矩阵中元素和为奇数的行数。
接下来的 $n$ 行，每行输出 $m$ 个整数 $a_{ij}$ ($0 \le a_{ij} \le 1$) — 矩阵的元素。
子任务
- （10 分）：$n, m \le 5$；
- （8 分）：矩阵中 $1$ 的总数不超过 $n$；
- （20 分）：每列中 $1$ 的个数不超过 $n/2$；
- （14 分）：$n, m \le 50$；
- （14 分）：$n \le 3\,000$；
- （14 分）：$n \cdot m \le 3 \cdot 10^5$；
- （20 分）：无附加限制。
如果你对某个子任务中的每个测试点都输出了正确的 $t$，你可以获得该子任务一半的分数。
请注意，要获得这部分分数，你需要输出正确的 $t$，并且：
- 要么不输出其他任何内容；即只输出 $t$，而不输出矩阵；
- 要么输出一个由 $0$ 和 $1$ 组成的完整矩阵，该矩阵不需要是正确的。例如，可以输出一个全 $0$ 矩阵。
如果你（在输出矩阵时）例如只输出了几行、输出了太多行、或者输出了除 $0$ 和 $1$ 以外的数字等，你将获得 $0$ 分。
对于第二个样例，获得一半分数的输出可以像这样：
2
或者像这样：
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
但不能像这样：
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
且不能像这样：
2 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
样例
输入 1
8 4 6 1 6 1
输出 1
6 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0
输入 2
4 4 3 0 3 0
输出 2
2 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0
输入 3
7 3 4 3 2
输出 3
7 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1
说明
在第一个样例中，第一列和第三列在至少 $4$ 个位置上相交（即在相同行都有 $1$），这意味着如果只有这两列，我们将有 $4$ 个偶数行。但由于还有两列各包含一个 $1$，我们可以将其中两个偶数行转化为奇数行，因此最优答案是 $6$ 个奇数行。
在第二个样例中，我们可以忽略第二列和第四列，因为它们没有 $1$，这意味着它们不会改变任何一行的奇偶性。而第一列和第三列在至少 $2$ 行相交，这意味着至少有两行是偶数行，因此答案是 $2$。
在第三个样例中，答案是 $7$，因为存在一个满足条件且有 $7$ 个奇数行的矩阵，且不存在拥有超过 $7$ 个奇数行的矩阵。