Yosupo's Algorithm

...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 the 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$)

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_1$

$\vdots$

$L_Q$ $R_Q$

For each query, print the maximum sum of weights of the selected points on its own line, 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