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