为了庆祝即将到来的儿童节，我们将举办一场糖果收集游戏。游戏在一个 $n \times m$ 的网格地图上进行。网格的行和列分别从 $1$ 到 $n$ 和 $1$ 到 $m$ 编号。

地图上有 $d$ 块糖果。第 $i$ 块糖果位于单元格 $(x_i, y_i)$，其甜度为 $s_i$。每个单元格最多包含一块糖果。

地图上有 $k$ 个棋子。最初，所有棋子都位于单元格 $(S_x, S_y)$。在每次操作中，玩家可以将一个棋子从 $(x, y)$ 移动到 $(x+1, y)$ 或 $(x, y+1)$。注意，一个单元格可以包含多个棋子。每当棋子位于包含糖果的单元格时，玩家就会拿走该糖果，当然，每块糖果不能被拿走超过一次。玩家可以进行任意次数的合法操作。玩家的最终得分等于所有被拿走的糖果的甜度之和。

地图上还有 $p$ 个矩形障碍物。假设第 $i$ 个矩形为 $[x_1, x_2] \times [y_1, y_2]$，则当且仅当 $x_1 \le x \le x_2$ 且 $y_1 \le y \le y_2$ 时，单元格 $(x, y)$ 被认为是危险的。玩家不应将棋子移动到任何危险单元格中。幸运的是：

• 地图边缘永远不会是危险的（即 $2 \le x_1 \le x_2 \le n - 1$，$2 \le y_1 \le y_2 \le m - 1$）。
• 没有任何两个障碍物会重叠或接触。换句话说，两个单元格 $(x, y)$ 和 $(x', y')$ 被认为是相邻的，当且仅当 $\max\{|x-x'|, |y-y'|\} \le 1$。如果有两个相邻的危险单元格，它们必须属于同一个障碍物。

你现在正在为这个糖果收集游戏进行训练。给定关于游戏的所有信息，尝试找出你能获得的最终得分的最大可能值。为了成为这个游戏的大师，你将进行 $q$ 次游戏重演，每次重演中起始单元格 $(S_x, S_y)$ 的位置和棋子数量 $k$ 可能会发生变化。

输入格式

第一行包含五个整数 $n, m, p, d$ 和 $q$ ($1 \le n, m \le 10^5$，$n \times m \le 10^6$，$0 \le p \le 10^5$，$1 \le d \le 2 \cdot 10^5$，$1 \le q \le 3 \cdot 10^5$)，分别表示地图的大小、障碍物的数量、糖果的数量以及游戏重演的次数。

接下来的 $p$ 行，每行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$ ($2 \le x_1 \le x_2 \le n - 1$，$2 \le y_1 \le y_2 \le m - 1$)，描述每个矩形障碍物。保证没有任何两个障碍物会重叠或接触。

接下来的 $d$ 行，每行包含三个整数 $x_i, y_i$ 和 $s_i$ ($1 \le x_i \le n$，$1 \le y_i \le m$，$1 \le s_i \le 10^9$)，描述每块糖果。保证每个单元格最多包含一块糖果，且没有糖果位于危险单元格中。

接下来的 $q$ 行，每行包含三个整数 $S_x, S_y$ 和 $k$ ($1 \le S_x \le n$，$1 \le S_y \le m$，$1 \le k \le 5$)，表示每次重演中起始单元格的位置和棋子数量。保证 $(S_x, S_y)$ 是安全的。

输出格式

输出 $q$ 行，第 $i$ 行 ($1 \le i \le q$) 包含一个整数，表示在第 $i$ 次重演中你能获得的最终得分的最大值。

样例

输入 1

3 3 1 4 5
2 2 2 2
1 1 1
3 3 1
1 2 3
2 1 5
1 1 1
1 1 2
1 3 2
1 2 2
2 1 1

输出 1

7
10
1
4
6

输入 2

5 7 1 3 4
2 3 3 4
3 1 1
2 2 10
5 4 100
1 2 1
1 2 2
1 1 2
2 7 1

输出 2

110
110
111
0