题目描述

在一个二维平面上，有 $N$ 个红点和 $N$ 个蓝点。

第 $i$ 个红点的坐标为 $(r_i^x,r_i^y)$，点权为 $r_i^w$；第 $i$ 个蓝点的坐标为 $(b_i^x,b_i^y)$，点权为 $b_i^w$。

给定 $Q$ 个询问。在第 $i$ 个询问中，给定两个整数 $L_i$ 和 $R_i$，你需要找到红点 $j$ 和蓝点 $k$，满足：

1. $r_j^y < b_k^y$；
2. 满足以下两个条件之一：

$$(r_j^x < L_i \text{ 且 } R_i < b_k^x) \quad\text{或}\quad (L_i < r_j^x \text{ 且 } b_k^x > R_i).$$

你需要求出这两个点的最大点权和，或者判断无解（即无法选出合法的 $j$ 和 $k$）。

输入格式

第一行一个正整数$N$，表示红点和蓝点的数量。

接下来$N$行，每行$3$个整数$r_i^x,r_i^y,r_i^w$，表示一个红点。

接下来$N$行，每行$3$个整数$b_i^x,b_i^y,b_i^w$，表示一个蓝点。

接下来一行一个正整数$Q$，表示询问次数。

接下来$Q$行，每行两个整数$L_i,R_i$，表示一个询问。

输出格式

对每个询问输出一行表示答案，如果无解输出$-1$。

样例输入

2
-3 1 1
-6 3 10
3 4 100
5 2 1000
5
-5 4
-2 6
-4 1
-10 10
-1 2

样例输出

101
-1
110
1001
1001

数据范围

本题采用子任务评测。对于所有数据，满足：

$1\leq N\leq 100000,1\leq Q\leq 500000$

$-1000000000\leq r_i^x,L_i\leq -1$，$1\leq b_i^x,R_i\leq 1000000000$

$1\leq r_i^y,b_i^y\leq 1000000000$

$1\leq r_i^w,b_i^w\leq 1000000000$

保证$r_1^x,...,r_N^x,b_1^x,...,b_N^x,L_1,...,L_Q,R_1,...,R_Q$互不相同

保证$r_1^y,...,r_N^y,b_1^y,...,b_N^y$互不相同

$subtask1:20pts$ $N,Q \leq 5000$

$subtask2:20pts$ $N,Q\leq 50000$

$subtask3:30pts$ $Q\leq 200000$

$subatsk 4:30pts$ 无特殊限制