시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB111100.000%

문제

...Can you replicate my master thesis in 5 hours?
Yosupo

You are given $N$ red points and $N$ blue points on a two dimensional plane. The $i$-th red point's coordinate is $(r^x_i, r^y_i)$, and its weight is $r^w_i$. The $i$-th blue point's coordinate is $(b^x_i, b^y_i)$, and its weight is $b^w_i$.

Process $Q$ queries. In the $i$-th query, you are given two integers $L_i$ and $R_i$, and choose a red point $j$ and a blue point $k$ with following conditions:

  • $r^y_j < b^y_k$
  • ($r^x_j < L_i$ and $R_i < b^x_k$) or ($L_i < r^x_j$ and $b^x_k < R_i$)

Your task is to maximize the sum of weights of the two points or report that it is impossible to select two points.

입력

Input is given from Standard Input in the following format:

$N$

$r^x_1$ $r^y_1$ $r^w_1$

$\vdots$

$r^x_N$ $r^y_N$ $r^w_N$

$b^x_1$ $b^y_1$ $b^w_1$

$\vdots$

$b^x_N$ $b^y_N$ $b^w_N$

$Q$

$L_1$ $R_2$

$\vdots$

$L_Q$ $R_Q$

출력

For each query, in a line, print the maximum sum of weights of the selected points, or $-1$ if it is impossible to choose two points.

제한

  • $1 \leq N \leq 100{,}000$
  • $1 \leq Q \leq 500{,}000$
  • $-1{,}000{,}000{,}000 \leq r^x_i, L_i \leq -1$
  • $1 \leq b^x_i, R_i \leq 1{,}000{,}000{,}000$
  • $1 \leq r^y_i, b^y_i \leq 1{,}000{,}000{,}000$
  • $1 \leq r^w_i, b^w_i \leq 1{,}000{,}000{,}000$
  • $r^x_1,\cdots,r^x_N,b^x_1,\cdots,b^x_N,L_1,\cdots,L_Q,R_1,\cdots,R_Q$ are all distinct
  • $r^y_1,\cdots,r^y_N,b^y_1,\cdots,b^y_N,$ are all distinct

예제 입력 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

예제 출력 1

101
-1
110
1001
1001

예제 입력 2

10
-389 786 414303478
-159 301 976196121
-268 599 754785437
-605 652 597104844
-199 841 214521748
-192 8 581825989
-515 898 509582353
-297 36 854072992
-489 616 41481895
-665 876 378086770
869 583 376652629
509 222 380009514
354 693 428231281
519 738 608396032
100 811 220629740
960 708 928349711
324 89 710139852
716 897 771429659
647 203 72269757
368 699 540753047
10
-350 499
-956 639
-287 504
-915 742
-777 135
-176 487
-150 987
-133 10
-852 147
-476 106

예제 출력 2

1564212844
1584592153
1782422703
1747625780
1196825861
1782422703
-1
1904545832
1196825861
1525454555