I. 星光指引前路
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

卡丘世界是一个二维平面,星绘在战地中放置了 $$$n$$$ 个星空之门,星空之门是一个矩形,能提供守护星芒获取护甲值。

形式化地,每个星空之门可以用 $$$(x_1,y_1,x_2,y_2,w)$$$ 表示,代表一个左上角坐标为 $$$(x_1,y_1)$$$ ,右下角坐标为 $$$(x_2,y_2)$$$ 的矩形,提供 $$$w$$$ 点护甲值。

战地中有 $$$m$$$ 位超弦体,第 $$$i$$$ 名超弦体位于 $$$(x_i,y_i)$$$ 的位置上,获取战场信息是非常重要的事情,所以超弦体 $$$i$$$ 好奇涵盖她的所有星空之门中提供第 $$$k_i$$$ 小的护甲值是多少?

一个星空之门 $$$(x_1,y_1,x_2,y_2)$$$ 能够涵盖一个超弦体 $$$(x,y)$$$ ,当且仅当 $$$x_1\leq x\leq x_2$$$ 且 $$$y_1\leq y\leq y_2$$$ 。

Input

第一行一个正整数 $$$n \ (n\leq 5 \times 10^4)$$$ 代表星空之门的个数。

第二行到第 $$$n+1$$$ 行,第 $$$i$$$ 行五个整数 $$$x_{1i},y_{1i},x_{2i},y_{2i},w_i$$$ ($$$|x_1|,|y_1|,|x_2|,|y_2|\leq 10^9$$$, $$$0 \lt w\leq 10^9$$$, $$$x_1\leq x_2$$$, $$$y_1\leq y_2$$$) ,含义如题所述 。

第 $$$n+2$$$ 行一个正整数 $$$m \ (m\leq 10^5)$$$ 代表超弦体数目。

接下来 $$$m$$$ 行,每行三个整数 $$$x_i,y_i,k_i$$$ ,意义如题所述,$$$|x|,|y|\leq 10^9, 1\leq k\leq n$$$ 。

Output

输出共 $$$m$$$ 行,第 $$$i$$$ 行代表第 $$$i$$$ 名超弦体想知道的信息。特别地,若涵盖其的星空之门数目不足 $$$k_i$$$ ,输出 $$$-1$$$ 。

Example
Input
3
0 0 4 4 1
-1 -1 3 5 9
2 1 9 3 4
2
1 1 2
2 5 3
Output
9
-1