题目描述

输入格式

第一行一个正整数$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$ 无特殊限制