# #769. 【NOI2022】二次整数规划问题

1. 一类约束是单个变量取值的约束：给出正整数 $k$（$3 \le k \le 5$）和 $n$ 个区间 $[l_i, r_i]$（$1 \le i \le n$），其中 $1 \le l_i \le r_i \le k$，你给出的序列需要满足 $\forall 1 \le i \le n$，$l_i \le x_i \le r_i$；
2. 另一类约束是变量之间取值的约束：给出 $m$ 个三元组 $(p_i, q_i, b_i)$，你给出的序列需要满足 $\forall 1 \le j \le m$，$| x_{p_j} - x_{q_j} | \le b_j$。

$$W(p_1, p_2, \cdots, p_n) = 10^6 G+\sum_{i=2}^{k-1} c_i v_i .$$

### 子任务

• $1 \le T \le 600$，
• 第 $i$ ($1 \le i \le T$) 个测试数据中，$1 \le n \le \max\left(\frac{T}{i},2 \log_2{T}\right)$，
• $3 \le k \le 5$，$0 \le m \le 3n$，$1 \le q,\sum q \le 3 \times 10^5$，
• $1 \le l_i \le r_i \le k$，
• $1 \le p_j,q_j \le n$，$0 \le b_j < k$，
• $0 \le v_2,\cdots,v_{k-1} \le {10}^{12}$。

$1$ $10$ $3$ $200$ $4$
$2$ $600$ $3 \times 10^5$ $6$
$3$ $10$ $4$ $200$ $4$
$4$ $600$ $3 \times 10^5$ $6$
$5$ $10$ $5$ $300$ $5$
$6$ $15$ $500$ $4$
$7$ $25$ $750$ $4$
$8$ $50$ $1000$ $6$
$9$ $80$ $1500$ $6$
$10$ $120$ $2000$ $5$
$11$ $200$ $8000$ A $3$
$12$ $400$ $3 \times 10^4$ $4$
$13$ $600$ $2 \times 10^5$ $5$
$14$ $200$ $8000$ B $3$
$15$ $400$ $3 \times 10^4$ $4$
$16$ $600$ $2 \times 10^5$ $4$
$17$ $120$ $10^5$ C $4$
$18$ $150$ $2 \times 10^5$ $5$
$19$ $180$ $3 \times 10^5$ $5$
$20$ $300$ $5 \times 10^4$ $5$
$21$ $450$ $10^5$ $4$
$22$ $600$ $3 \times 10^5$ $4$
• 特殊性质 A：$m=0$。
• 特殊性质 B：$m \le 10$，单个测试点中所有测试数据的 $m$ 的和不超过 $200$。
• 特殊性质 C：数据随机生成。具体地，生成测试点中每组测试数据时，给出参数 $k,n,m,q$ 以及 $k$ 个非负整数 $p_0, p_1, p_2, \cdots,p_{k-1}$，保证 $p_{k-1} \neq 0$，则按照如下规则生成该组数据：
• 对于 $1 \le i \le n$，独立均匀生成 $x,y \in [1,k]$，则 $l_i=\min(x,y),r_i=\max(x,y)$；
• 不断按照如下方式生成三元组直至有 $m$ 个三元组：
1. 独立均匀随机生成 $u,v \in [1,n]$；
2. 以 $p$ 为权值随机生成 $w$（对于 $0 \le i \le k-1$，$w=i$ 的概率为 $\frac{p_i}{p_0 + p_1 + \cdots + p_{k-1}}$）；
3. 若在原有三元组集合中加入 $(u,v,w)$ 后不存在序列 $(x_1,x_2,\cdots,x_n)$ 满足所有限制，则舍弃当前三元组，否则加入当前三元组。
• 每组询问的 $v_2, \cdots, v_{k-1}$ 在 $[0,10^{12}]$ 内独立均匀随机生成。