LIS on Grid#12944

LIS on Grid

You are given a grid with rows and columns. rows are numbered from to from top to bottom, and columns are numbered from to from left to right. Let's denote the cell at the intersection of the -th row and the -th column by .

You have to color some of these cells in black. More precisely, in -th column you should color exactly a_i cells in black.

After you color cells of your choice, your penalty will be calculated as the length of the longest increasing subsequence of black cells. More precisely, it will be equal to the largest , for which there exists a sequence of cells (r_1, c_1), (r_2, c_2), \ldots, (r_k, c_k), such that:

Find the smallest possible penalty you can get.

Input

The first line contains a single integer (1 \le t \le 10^5)  — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers (1 \leq n, m \leq 2\cdot 10^5, m\cdot n\leq 2\cdot 10^5)  — the numbers of rows and columns correspondingly.

The second line of each test case contains integers a_1, a_2, \ldots, a_m (1 \le a_i \le n), indicating that you have to color exactly a_i cells in column .

It is guaranteed that the sum of m\cdot n over all test cases does not exceed 2\cdot 10^5.

Output

For each test case, in the first line output a single integer  — the smallest penalty you can achieve.

In the next lines, output strings. -th string should have length and consist only of characters . and #. If -th character of -th string is #, cell is colored black, otherwise it's colored white.

Examples

Example

Loading
Loading