题目描述

在一个二维平面上，有$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 \ and\ R_i<b_k^x)\ or\ (L_i<r_j^x \ and\ 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$ 无特殊限制