In this problem, you need to solve a famous NP-hard problem: the Quadratic Integer Programming problem.
The Quadratic Integer Programming problem involves variables: you need to provide an integer sequence $(x_1, x_2, \dots, x_n)$ of length $n$ that satisfies all the conditions below.
The Quadratic Integer Programming problem has constraints: the integer sequence you provide must satisfy the following two types of constraints: 1. One type of constraint is on the values of individual variables: given a positive integer $k$ ($3 \le k \le 5$) and $n$ intervals $[l_i, r_i]$ ($1 \le i \le n$), where $1 \le l_i \le r_i \le k$, your sequence must satisfy $\forall 1 \le i \le n, l_i \le x_i \le r_i$. 2. Another type of constraint is on the values between variables: given $m$ triples $(p_j, q_j, b_j)$, your sequence must satisfy $\forall 1 \le j \le m, |x_{p_j} - x_{q_j}| \le b_j$.
The Quadratic Integer Programming problem has an objective function: given $k-2$ weight parameters $v_2, v_3, \dots, v_{k-1}$ (note that the index range is $2$ to $k-1$), for an integer sequence $\{p_1, p_2, \dots, p_n\}$ with a domain of $[1, k]$, let $c_i$ be the number of elements in the sequence that take the value $i$, and $G$ be the number of integer pairs $(i, j)$ such that $1 \le i, j \le n$ and $|p_i - p_j| \le 1$. Note that when $i \neq j$, $(i, j)$ and $(j, i)$ are distinct pairs. The weight of this sequence is defined as: $$W(p_1, p_2, \dots, p_n) = 10^6 G + \sum_{i=2}^{k-1} c_i v_i$$
Your sequence must maximize this weight while satisfying the two types of constraints mentioned above.
The Quadratic Integer Programming problem does not necessarily have multiple queries, but we will provide $q$ queries. Each query provides different weight parameters $v_2, v_3, \dots, v_{k-1}$. For each query, you need to find the sequence that satisfies the constraints and maximizes the weight. To reduce the output volume, you only need to output the weight of this sequence.
Input
Read the data from the file qip.in.
There are multiple test cases. The first line contains a non-negative integer and a positive integer $C, T$, representing the test point number and the number of test cases, respectively. $C = 0$ indicates that this set of data is a sample.
For each test case, the first line contains four integers $k, n, m, q$, describing the domain of the sequence, the length of the sequence, the number of constraints between variables, and the number of queries.
The next $n$ lines each contain two integers $l_i, r_i$, describing the value interval for each element in the sequence.
The next $m$ lines each contain three integers $p_j, q_j, b_j$, describing a constraint between variables.
The next $q$ lines each contain $k-2$ non-negative integers $v_2, v_3, \dots, v_{k-1}$, describing the weight parameters for a query.
Output
Output to the file qip.out.
For each query in each test case, output one integer per line, representing the maximum value of the sequence weight.
Subtasks
Let $\sum q$ be the sum of $q$ for all test cases in a single test point. For all test points: $1 \le T \le 600$, In the $i$-th ($1 \le i \le T$) test case, $1 \le n \le \max(\frac{T}{i}, 2 \log_2 T)$, $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, \dots, v_{k-1} \le 10^{12}$.
| Test Point ID | $T \le$ | $k=$ | $\sum q \le$ | Special Property | Points |
|---|---|---|---|---|---|
| 1 | 10 | 3 | 200 | None | 4 |
| 2 | 600 | 3 | $3 \times 10^5$ | None | 6 |
| 3 | 10 | 4 | 200 | None | 4 |
| 4 | 600 | 4 | $3 \times 10^5$ | None | 6 |
| 5 | 10 | 5 | 300 | None | 5 |
| 6 | 15 | 5 | 500 | None | 4 |
| 7 | 25 | 5 | 750 | None | 4 |
| 8 | 50 | 5 | 1000 | None | 6 |
| 9 | 80 | 5 | 1500 | None | 6 |
| 10 | 120 | 5 | 2000 | None | 5 |
| 11 | 200 | 5 | 8000 | A | 3 |
| 12 | 400 | 5 | $3 \times 10^4$ | A | 4 |
| 13 | 600 | 5 | $2 \times 10^5$ | A | 5 |
| 14 | 200 | 5 | 8000 | B | 3 |
| 15 | 400 | 5 | $3 \times 10^4$ | B | 4 |
| 16 | 600 | 5 | $2 \times 10^5$ | B | 4 |
| 17 | 120 | 5 | $10^5$ | C | 4 |
| 18 | 150 | 5 | $2 \times 10^5$ | C | 5 |
| 19 | 180 | 5 | $3 \times 10^5$ | C | 5 |
| 20 | 300 | 5 | $5 \times 10^4$ | None | 5 |
| 21 | 450 | 5 | $10^5$ | None | 4 |
| 22 | 600 | 5 | $3 \times 10^5$ | None | 4 |
Special Property A: $m = 0$.
Special Property B: $m \le 10$, and the sum of $m$ over all test cases in a single test point does not exceed 200.
Special Property C: Data is randomly generated. Specifically, when generating each test case in a test point, given parameters $k, n, m, q$ and $k$ non-negative integers $p_0, p_1, p_2, \dots, p_{k-1}$, ensuring $p_{k-1} \neq 0$, the data is generated according to the following rules: For $1 \le i \le n$, independently and uniformly generate $x, y \in [1, k]$, then $l_i = \min(x, y), r_i = \max(x, y)$; Continuously generate triples in the following way until there are $m$ triples: 1. Independently and uniformly generate $u, v \in [1, n]$; 2. Randomly generate $w$ with weights $p$ (for $0 \le i \le k-1$, the probability that $w = i$ is $\frac{p_i}{p_0 + p_1 + \dots + p_{k-1}}$); 3. If adding $(u, v, w)$ to the existing set of triples results in no sequence $(x_1, x_2, \dots, x_n)$ satisfying all constraints, discard the current triple; otherwise, add it. * The $v_2, \dots, v_{k-1}$ for each query are independently and uniformly generated in $[0, 10^{12}]$.
Examples
Input 1
qip/qip1.in
Output 1
qip/qip1.ans
Input 2
qip/qip2.in
Output 2
qip/qip2.ans
Input 3
qip/qip3.in
Output 3
qip/qip3.ans
Input 4
qip/qip4.in
Output 4
qip/qip4.ans
Input 5
qip/qip5.in
Output 5
qip/qip5.ans
Input 6
qip/qip6.in
Output 6
qip/qip6.ans
Input 7
qip/qip7.in
Output 7
qip/qip7.ans
Input 8
qip/qip8.in
Output 8
qip/qip8.ans