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$$$.
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$$$.
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.
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
1 01100 -1 0 000 160 01001100 7168 010100