D. Nanami and the Constructive Problem
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nanami has given you an array $$$a$$$ of length $$$n$$$ which she needs you to color.

But before you color it, she gives you $$$m$$$ requirements, each of which is denoted as $$$x,y,l,r(x\neq y;0\le l\le r \le 2)$$$, which means that for two positions $$$x,y$$$, the number of positions that are colored must be greater than or equal to $$$l$$$ and less than or equal to $$$r$$$.

Nanami wants to ask you, what is the smallest possible value of the maximum minus the minimum of the numbers of all the colored positions, provided that all the $$$m$$$ requirements are met?

If no position is colored, then the value is $$$0$$$.

Input

In the first line, an integer $$$t(1\le t\le 10^4)$$$, representing the number of data sets.

For each group of data:

First row, two integers $$$n,m(2\le n\le 10^5;1\le m\le 10^5)$$$, representing the length of the array and the number of coloring requirements.

Second row, $$$n$$$ integers $$$a_1,a_2,\dots,a_n(-10^8\le a_i \le 10^8)$$$, representing the array $$$a$$$.

The third to $$$m+2$$$ rows, each with four integers $$$x,y,l,r(1\le x,y\le n;x\neq y;0\le l\le r \le 2)$$$, represent a coloring request.

It is guaranteed that the sum of $$$n+m$$$ within the same test point will not exceed $$$10^5$$$.

Output

For each set of data, if a coloring scheme exists, then first output a line of integers representing the maximum minus the smallest possible minimum value of the digits at all positions that are colored. Next, on the second line, output a binary string $$$s$$$ of length $$$n$$$. If $$$s_i=0$$$, the $$$i$$$th position is not colored; if $$$s_i=1$$$, the $$$i$$$th position is colored.

If no color scheme exists, only one integer line $$$-1$$$ is output.

Any coloring scheme that satisfies the requirements of the question is considered correct.

Example
Input
5
5 2
-1 2 1 3 100
2 1 1 2
3 5 1 2
2 2
0 0
1 2 0 0
1 2 1 1
3 1
916 916 916
1 3 0 2
8 4
62 -43 -27 -25 73 -87 17 34
4 5 1 2
4 6 0 1
2 6 2 2
2 7 0 2
6 5
-4458 8270 5697 1102 2620 -5323
1 5 0 1
2 6 0 1
4 2 2 2
2 1 0 1
5 2 1 1
Output
1
01100
-1
0
000
160
01001100
7168
010100