题目描述

一台校准仪有内、外两圈刻度。每圈都被等分为 $L$ 个位置，按顺时针方向编号为 $0,1,\ldots,L-1$。

内圈可以转动，上面有 $n$ 条刻痕。第 $i$ 条内圈刻痕初始位于位置 $a_i$，符号为 $c_i$，清晰度为 $w_i$。外圈固定不动，上面有 $m$ 条参考刻痕。第 $j$ 条外圈刻痕位于位置 $b_j$，符号为 $d_j$，清晰度为 $v_j$。同一圈内的刻痕位置两两不同。

将内圈顺时针转动 $x$ 格后，第 $i$ 条内圈刻痕位于

如果一条内圈刻痕与一条外圈刻痕位于同一位置，并且它们的符号相同，就形成一次有效重合，其贡献为两条刻痕清晰度的较小值。一次转动的校准得分是所有有效重合的贡献之和。

若一次转动产生了至少一次有效重合，则称它是合法校准。保证至少存在一种合法校准。

你需要在所有 $0\le x<L$ 的合法校准中，找到得分最大的转动格数 $x$。若有多个 $x$ 的得分相同，选择其中最小的 $x$。

输入格式

从文件 calibrate.in 中读取数据。

第一行包含四个整数 $L,n,m,q$，分别表示每圈的位置数、内圈刻痕数、外圈刻痕数和符号种数。

接下来 $n$ 行，第 $i$ 行包含三个整数 $a_i,c_i,w_i$，描述一条内圈刻痕。

接下来 $m$ 行，第 $j$ 行包含三个整数 $b_j,d_j,v_j$，描述一条外圈刻痕。

输出格式

输出到文件 calibrate.out 中。

输出两个整数 $x$ 和 $s$，分别表示按题目规则选出的转动格数和对应的最大校准得分。由于规定了得分相同时选择最小的 $x$，这两个整数唯一确定。

样例

12 3 4 2
1 1 5
5 2 7
9 1 4
3 1 6
7 2 3
11 1 8
4 2 10

2 12

样例解释

样例 #1 中，将内圈顺时针转动 $2$ 格后，三条内圈刻痕分别到达位置 $3,7,11$。它们均与相同符号的外圈刻痕重合，贡献依次为 $5,3,4$，总得分为 $12$。不存在得分更高的合法校准。

数据规模与约定

对于所有数据，保证：

• $2\le L\le 200000$；
• $1\le n,m\le \min(L,2000)$，且 $n\times m\le 4\times 10^6$；
• $1\le q\le 200000$；
• $0\le a_i,b_j<L$；
• $1\le c_i,d_j\le q$；
• $1\le w_i,v_j\le 10^9$；
• $a_1,a_2,\ldots,a_n$ 两两不同，$b_1,b_2,\ldots,b_m$ 两两不同；
• 至少存在一对下标 $i,j$ 满足 $c_i=d_j$；
• 最大校准得分不超过 $2\times 10^{12}$。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

各子任务的分值和额外约束如下。子任务 $1$ 的额外约束蕴含子任务 $2$ 的额外约束，子任务 $2$ 的额外约束蕴含子任务 $3$ 的额外约束。

下发文件

下载三组测试数据，非真实测试数据