给定一个 $n$ 行 $m$ 列的网格。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。我们将第 $i$ 行第 $j$ 列的单元格记为 $(i, j)$。

你需要将其中一些单元格涂成黑色。具体来说，在第 $i$ 列中，你需要恰好将 $a_i$ 个单元格涂成黑色。

在你选择涂色后，你的惩罚值将计算为黑色单元格构成的最长上升子序列的长度。更准确地说，它等于最大的 $k$，使得存在一个单元格序列 $(r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)$，满足：

• $1 \le r_1 < r_2 < \dots < r_k \le n$
• $1 \le c_1 < c_2 < \dots < c_k \le m$
• 所有单元格 $(r_i, c_i)$ 均为黑色

求你能得到的最小惩罚值。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($1 \le n, m \le 2 \cdot 10^5, m \cdot n \le 2 \cdot 10^5$)，分别表示行数和列数。

每个测试用例的第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$)，表示你必须在第 $i$ 列中涂黑恰好 $a_i$ 个单元格。

保证所有测试用例中 $m \cdot n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，第一行输出一个整数，表示你能达到的最小惩罚值。

接下来的 $n$ 行，输出 $n$ 个字符串。第 $i$ 个字符串长度应为 $m$，且仅由字符 . 和 # 组成。如果第 $i$ 个字符串的第 $j$ 个字符为 #，则单元格 $(i, j)$ 被涂成黑色，否则涂成白色。

样例

样例输入 1

4
2 4
1 1 1 1
3 3
3 3 3
4 4
4 3 2 1
4 5
2 3 4 3 2

样例输出 1

1
....
####
3
###
###
###
2
###.
#...
####
##..
2
..###
.####
####.
###..