Problem Description

In this problem, you need to solve a famous NP problem—the quadratic integer programming problem.

The quadratic integer programming problem has variables: you need to give an integer sequence $(x_1, x_2, \ldots, x_n)$ of length $n$ that satisfies all conditions below.

The quadratic integer programming problem has constraints: the integer sequence you give must satisfy the following two types of constraints:

1. The first type constrains the value of each single variable: given a positive integer $k$ ($3 \leq k \leq 5$) and $n$ intervals $[l_i, r_i]$ ($1 \leq i \leq n$), where $1 \leq l_i \leq r_i \leq k$, your sequence must satisfy $\forall 1 \leq i \leq n$, $l_i \leq x_i \leq r_i$.
2. The second type constrains the values between variables: given $m$ triples $(p_i, q_i, b_i)$, your sequence must satisfy $\forall 1 \leq j \leq m$, $\lvert x_{p_j} - x_{q_j} \rvert \leq b_j$.

The quadratic integer programming problem has an objective function: given $k-2$ objective parameters $v_2,v_3,\dots,v_{k-1}$ (note that the index range is from $\boldsymbol{2}$ to $\boldsymbol{k-1}$), for an integer sequence $\{p_1,p_2,\dots,p_n\}$ with value range $[1,k]$, let $c_i$ be the number of elements in the sequence whose value equals $i$, and let $G$ be the number of integer ordered pairs $(i, j)$ satisfying $1 \leq i,j \leq n$ and $|p_i-p_j|\leq 1$. Note that when $\boldsymbol{i \neq j}$, $\boldsymbol{(i, j)}$ and $\boldsymbol{(j, i)}$ are different ordered pairs. Define the weight of this sequence as

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

Your sequence needs to maximize its weight while satisfying the two types of constraints above. It is guaranteed that, under the given constraints, there exists a sequence that satisfies them.

The quadratic integer programming problem does not have to include multiple queries, but we will give $q$ queries. Each query provides different weight parameters $v_2, v_3, \ldots, v_{k-1}$. For each query, you need to find a sequence that satisfies the constraints and maximizes the weight. To reduce the output size, you only need to output the weight of this sequence.

Input Format

This problem contains multiple test cases. The first line contains a non-negative integer and a positive integer $C, T$, representing the test point ID and the number of testdata. $C = 0$ indicates that this set of data is a sample.

For each testdata, the first line contains four integers $k, n, m, q$, describing the sequence value range, the sequence length, 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 allowed value interval for each element in the sequence.

The next $m$ lines each contain three integers $p_j, q_j, b_j$, describing one constraint between variables.

The next $q$ lines each contain $k - 2$ non-negative integers $v_2, v_3, \ldots, v_{k - 1}$, describing the weight parameters of one query.

Output Format

For each query of each testdata, output one line containing one integer, representing the maximum possible weight of the sequence.

Hint

[Sample #1]

See qip/qip1.in and qip/qip1.ans in the attachment.

This sample satisfies the property of test point $1$ in the Constraints.

---

[Sample Explanation #1]

In the first testdata, the optimal sequence for both queries is $(1, 2, 2, 1, 3)$, where $c_2 = 2, G = 21$.

---

[Sample #2]

See qip/qip2.in and qip/qip2.ans in the attachment.

This sample satisfies the property of test point $3$ in the Constraints.

---

[Sample Explanation #2]

In the first testdata, the optimal sequences for the two queries are $(4,4,3,3)$ and $(4,3,2,2)$.

---

[Sample #3]

See qip/qip3.in and qip/qip3.ans in the attachment.

This sample satisfies the property of test point $5$ in the Constraints.

---

[Sample Explanation #3]

In the first testdata, one optimal sequence for the three queries is $(3, 3, 3, 3, 3)$, $(2, 2, 3, 3, 2)$, and $(3, 2, 4, 4, 2)$.

---

[Sample #4]

See qip/qip4.in and qip/qip4.ans in the attachment.

This sample satisfies the property of test point $2$ in the Constraints.

---

[Sample #5]

See qip/qip5.in and qip/qip5.ans in the attachment.

This sample satisfies the property of test point $4$ in the Constraints.

---

[Sample #6]

See qip/qip6.in and qip/qip6.ans in the attachment.

This sample satisfies the property of test point $8$ in the Constraints.

---

[Sample #7]

See qip/qip7.in and qip/qip7.ans in the attachment.

This sample satisfies the property of test point $14$ in the Constraints.

---

[Sample #8]

See qip/qip8.in and qip/qip8.ans in the attachment.

This sample satisfies the property of test point $17$ in the Constraints.

---

[Constraints]

Let $\sum q$ be the sum of $q$ over all testdata in a single test point. For all test points,

• $1 \leq T \leq 600$.
• In the $i$-th ($1 \le i \le T$) testdata, $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<k$.
• $0 \leq v_2,\dots,v_{k-1} \leq 10^{12}$.

Test Point ID	$T \leq$	$k=$	$\sum q \leq$	Special Property	Score
$1$	$10$	$3$	$200$	None	$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$
$8$	$50$		$1000$		$6$
$9$	$80$		$1500$
$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$
$17$	$120$		$10^5$	C
$18$	$150$		$2 \times 10^5$		$5$
$19$	$180$		$3 \times 10^5$
$20$	$300$		$5 \times 10^4$	None
$21$	$450$		$10^5$		$4$
$22$	$600$		$3 \times 10^5$

Special Property A: $m=0$.

Special Property B: $m \leq 10$, and the sum of $m$ over all testdata in a single test point does not exceed $200$.

Special Property C: The data is generated randomly. Specifically, when generating each testdata in the test point, parameters $k,n,m,q$ and $k$ non-negative constants $p_0,p_1,p_2,\dots,p_{k-1}$ are given, and it is guaranteed that $p_{k-1} \neq 0$. Then the data is generated by the following rules:

• For $1 \leq i \leq n$, independently generate $x,y \in [1,k]$ uniformly at random, then $l_i=\min(x,y),r_i=\max(x,y)$.
• Repeatedly generate triples as follows until there are $m$ triples:
  1. Independently generate $u,v \in [1,n]$ uniformly at random.
  2. Randomly generate $w$ with weights $p$ (for $0 \leq i \leq k-1$, the probability that $w=i$ is $\frac{p_i}{p_0+p_1+\dots+p_{k-1}}$).
  3. If after adding $(u,v,w)$ to the existing set of triples, there is no sequence $(x_1,x_2,\dots,x_n)$ satisfying all constraints, then discard this triple; otherwise, keep it.
• For each query, $v_2, \ldots, v_{k-1}$ are independently generated uniformly at random in $[0,10^{12}]$.

Translated by ChatGPT 5