P8501 [NOI2022] 二次整数规划问题

本题中，你需要解决一个著名的 NP 问题——二次整数规划问题。 二次整数规划问题要有变量：你需要给出一个长度为 $n$ 的**整数**序列 $(x_1, x_2, \ldots, x_n)$，满足下文中的所有条件。 二次整数规划问题要有约束：你给出的整数序列需要满足以下两类约束： 1. 一类约束是单个变量取值的约束：给出正整数 $k$（$3 \leq k \leq 5$）和 $n$ 个区间 $[l_i, r_i]$（$1 \leq i \leq n$），其中 $1 \leq l_i \leq r_i \leq k$，你给出的序列需要满足 $\forall 1 \leq i \leq n$，$l_i \leq x_i \leq r_i$； 2. 另一类约束是变量之间取值的约束：给出 $m$ 个三元组 $(p_i, q_i, b_i)$，你给出的序列需要满足 $\forall 1 \leq j \leq m$，$\lvert x_{p_j} - x_{q_j} \rvert \leq b_j$。 二次整数规划问题要有目标函数：在给出 $k-2$ 个目标参数 $v_2,v_3,\dots,v_{k-1}$（**注意下标范围为 $\boldsymbol{2}$ 至 $\boldsymbol{k-1}$**）的前提下，对于一个值域为 $[1,k]$ 的整数数列 $\{p_1,p_2,\dots,p_n\}$，设 $c_i$ 为该序列中取值为 $i$ 的元素个数，$G$ 为满足 $1 \leq i,j \leq n$ 且 $|p_i-p_j|\leq 1$ 的整数二元组 $(i, j)$ 个数，**注意当 $\boldsymbol{i \neq j}$ 时，$\boldsymbol{(i, j)}$ 与 $\boldsymbol{(j, i)}$ 是不同的二元组**。定义该序列的**权值**为 $$ W(p_1, p_2, \ldots, p_n) = 10^6 G+\sum_{i=2}^{k-1} c_i v_i \text{。} $$ 你的序列需要在满足以上两类约束的情况下，最大化其权值。在给出的约束下，保证存在满足约束的序列。 二次整数规划问题不一定要有多组询问，但是我们会给出 $q$ 次询问，每次询问给出不同的权值参数 $v_2, v_3, \ldots, v_{k-1}$，对于每组询问你需要找到满足约束的最大化权值的序列。为了减少输出量，你只需要输出这个序列的权值。

**本题有多组测试数据。** 第一行一个非负整数和一个正整数 $C, T$，分别表示测试点编号和测试数据数量。$C = 0$ 表示该组数据为样例。 对于每组测试数据，第一行四个整数 $k, n, m, q$，描述序列值域、序列长度、变量之间约束的个数和询问次数。 接下来 $n$ 行每行两个整数 $l_i, r_i$，描述序列中每个元素对应的取值区间。 接下来 $m$ 行每行三个整数 $p_j, q_j, b_j$，描述一个变量之间的约束。 接下来 $q$ 行每行 $k - 2$ 个非负整数 $v_2, v_3, \ldots, v_{k - 1}$ 描述一组询问的权值参数。

对于每组数据的每组询问输出一行一个整数，表示序列权值的最大值。

**【样例 \#1】** 见附件中的 `qip/qip1.in` 与 `qip/qip1.ans`。 该样例满足数据范围中测试点 $1$ 的性质。 ---- **【样例解释 \#1】** 第一个测试数据中两组询问对应的最优序列均为 $(1, 2, 2, 1, 3)$，有 $c_2 = 2, G = 21$。 ---- **【样例 \#2】** 见附件中的 `qip/qip2.in` 与 `qip/qip2.ans`。 该样例满足数据范围中测试点 $3$ 的性质。 ---- **【样例解释 \#2】** 第一个测试数据中两组询问对应的最优序列分别为 $(4,4,3,3)$ 和 $(4,3,2,2)$。 ---- **【样例 \#3】** 见附件中的 `qip/qip3.in` 与 `qip/qip3.ans`。 该样例满足数据范围中测试点 $5$ 的性质。 ---- **【样例解释 \#3】** 第一个测试数据中三组询问对应的一个最优序列分别为 $(3, 3, 3, 3, 3)$、$(2, 2, 3, 3, 2)$ 和 $(3, 2, 4, 4, 2)$。 ---- **【样例 \#4】** 见附件中的 `qip/qip4.in` 与 `qip/qip4.ans`。 该样例满足数据范围中测试点 $2$ 的性质。 ---- **【样例 \#5】** 见附件中的 `qip/qip5.in` 与 `qip/qip5.ans`。 该样例满足数据范围中测试点 $4$ 的性质。 ---- **【样例 \#6】** 见附件中的 `qip/qip6.in` 与 `qip/qip6.ans`。 该样例满足数据范围中测试点 $8$ 的性质。 ---- **【样例 \#7】** 见附件中的 `qip/qip7.in` 与 `qip/qip7.ans`。 该样例满足数据范围中测试点 $14$ 的性质。 ---- **【样例 \#8】** 见附件中的 `qip/qip8.in` 与 `qip/qip8.ans`。 该样例满足数据范围中测试点 $17$ 的性质。 ---- **【数据范围】** 设 $\sum q$ 为单个测试点中所有测试数据的 $q$ 的和。对于所有测试点， - $1 \leq T \leq 600$， - 第 $i$（$1 \le i \le T$）个测试数据中，$1 \leq n \leq \max(\frac{T}{i},2 \log_2 T)$， - $3 \leq k \leq 5$，$0 \leq m \leq 3n$，$1 \leq q,\sum q \leq 3 \times 10^5$， - $1 \leq l_i \leq r_i \leq k$， - $1 \leq p_j,q_j \leq n$，$0 \leq b_j