本题中，你需要解决一个著名的 NP 问题——二次整数规划问题。

二次整数规划问题要有变量：你需要给出一个长度为 $n$ 的整数序列 $(x_1,x_2,\cdots ,x_n)$，满足下文中的所有条件。

二次整数规划问题要有约束：你给出的整数序列需要满足以下两类约束：

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$，你给出的序列需要满足 $\mathrm{\forall }1\le i\le n$，$l_i\le x_i\le r_i$；
2. 另一类约束是变量之间取值的约束：给出 $m$ 个三元组 $(p_i,q_i,b_i)$，你给出的序列需要满足 $\mathrm{\forall }1\le j\le m$，$|x_{p_j}-x_{q_j}|\le b_j$。

二次整数规划问题要有目标函数：在给出 $k-2$ 个目标参数 $v_2,v_3,\cdots ,v_{k-1}$（注意下标范围为 $2$ 至 $k-1$）的前提下，对于一个值域为 $[1,k]$ 的整数数列 $\{p_1,p_2,\cdots ,p_n\}$，设 $c_i$ 为该序列中取值为 $i$ 的元素个数，$G$ 为满足 $1\le i,j\le n$ 且 $|p_i-p_j|\le 1$ 的整数二元组 $(i,j)$ 个数，注意当 $i\ne j$ 时，$(i,j)$ 与 $(j,i)$ 是不同的二元组。定义该序列的权值为

$$W(p_1,p_2,\cdots ,p_n)={10}^{6}G+\sum _{i=2}^{k-1}{c}_i{v}_i.$$

你的序列需要在满足以上两类约束的情况下，最大化其权值。

二次整数规划问题不一定要有多组询问，但是我们会给出 $q$ 次询问，每次询问给出不同的权值参数 $v_2,v_3,\cdots ,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,\cdots ,v_{k-1}$ 描述一组询问的权值参数。

数据保证在给定的约束条件下，至少存在一组满足所有约束的序列。

输出格式

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

样例一

见附件下载。

该样例满足数据范围中测试点 $1$ 的性质。

explanation

第一个测试数据中两组询问对应的最优序列均为 $(1,2,2,1,3)$，有 $c_2=2,G=21$。

样例二

见附件下载。

该样例满足数据范围中测试点 $3$ 的性质。

explanation

第一个测试数据中两组询问对应的一个最优序列分别为 $(4,4,3,3)$ 和 $(4,3,2,2)$。

样例三

见附件下载。

该样例满足数据范围中测试点 $5$ 的性质。

explanation

第一个测试数据中三组询问对应的一个最优序列分别为 $(3,3,3,3,3)$、$(2,2,3,3,2)$ 和 $(3,2,4,4,2)$。

样例四

见附件下载。

该样例满足数据范围中测试点 $2$ 的性质。

样例五

见附件下载。

该样例满足数据范围中测试点 $4$ 的性质。

样例六

见附件下载。

该样例满足数据范围中测试点 $8$ 的性质。

样例七

见附件下载。

该样例满足数据范围中测试点 $14$ 的性质。

样例八

见附件下载。

该样例满足数据范围中测试点 $17$ 的性质。

子任务

设 $\sum q$ 为单个测试点中所有测试数据的 $q$ 的和。对于所有测试点，

• $1\le T\le 600$，
• 第 $i$ ($1\le i\le T$) 个测试数据中，$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,\cdots ,v_{k-1}\le {10}^{12}$。

• 特殊性质 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}\ne 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}]$ 内独立均匀随机生成。

时间限制：2s$\mathtt{\text{3s}}$

空间限制：$1\mathtt{\text{GB}}$