seuOJ512 - Nanami and the Constructive Problem

题目描述

Nanami 长大上学了，遇到了一道作业题。

有一个长度为 nn 的数组 aa，她需要给这个数组涂色。

但在涂色之前，还有 mm 个要求，每个要求被表示成 x,y,l,r(x≠y;0≤l≤r≤2)x,y,l,r(x\neq y;0\le l\le r \le 2)，代表对于 x,yx,y 两个位置，其中被涂色的位置的数量必须大于等于 ll 并且小于等于 rr。

请问，在满足所有的 mm 个要求的前提下，被涂色的所有位置的数字的最大值减去最小值可能的最小值是多少呢？

假如没有位置被涂色，那么这个值为 00。

输入格式

第一行，一个整数 t(1≤t≤104)t(1\le t\le 10^4)，代表数据组数。

对于每组数据：

第一行，两个整数 n,m(2≤n≤105;1≤m≤105)n,m(2\le n\le 10^5;1\le m\le 10^5)，代表数组长度与涂色要求数量。

第二行，nn 个整数 a1,a2,…,an(−108≤ai≤108)a_1,a_2,\dots,a_n(-10^8\le a_i \le 10^8)，代表数组 aa。

第三至 m+2m+2 行，每行四个整数 x,y,l,r(1≤x,y≤n;x≠y;0≤l≤r≤2)x,y,l,r(1\le x,y\le n;x\neq y;0\le l\le r \le 2)，代表一个涂色要求。

保证同一测试点内 n+mn+m 的和不会超过 10510^5。

输出格式

对于每组数据，如果存在涂色方案，那么先输出一行整数，代表被涂色的所有位置的数字的最大值减去最小值可能的最小值。 接下来，在第二行，输出一个长度为 nn 的二进制字符串 ss。如果 si=0s_i=0，代表第 ii 个位置没有被涂色；如果 si=1s_i=1，代表第 ii 个位置被涂色。

如果不存在涂色方案，只输出一行整数 −1-1。

任何符合题目要求的方案都是正确的。

样例

输入样例

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