D : Japanese Origami No.1

背景

kagamiz 君は塗り絵が大好きです. しかし塗り絵をしすぎてもう普通の塗り絵では満足できない体になってしまいました.

kagamiz「これはもう$x$ - $y$ 平面を塗るしかないみたいですね…」

問題

$x$ - $y$ 平面を考える. このとき, 以下のクエリを処理せよ.

まず, $N$ 個の塗りつぶしクエリが与えられる.
$i$ 番目の塗りつぶしクエリでは, 整数 $L_i,\ R_i,\ H_i$ が与えられる. このとき, $L_i \leqq x \leqq R_i$ かつ $0 \leqq y \leqq H_i$ となる長方形領域の色をすべて色 $i$ に上書きする.

次に, $M$ 個の調査クエリが与えられる.
$i$ 番目の調査クエリでは, 整数 $P_i$ が与えられる. このとき,直線 $x = P_i$ と重なる色は何種類かを答える. ただし, どの塗りつぶしクエリでも色が変更されていない領域については考慮しない(色の個数に含めない).

入力

$N$ $L_1$ $R_1$ $H_1$ $L_2$ $R_2$ $H_2$ $\vdots$ $L_N$ $R_N$ $H_N$ $M$ $P_1$ $P_2$ $\vdots$ $P_M$

出力

出力は $M$ 行からなる. $i$ 行目には, $i$ 番目の調査クエリの解となる整数を出力せよ.

制約

全てのデータセットでは以下の制約を満たす.

• $1 \leqq N \leqq 100,000.$
• $1 \leqq L_i \lt R_i \leqq 400,001.$
• $1 \leqq H_i \leqq 100,000.$
• $1 \leqq M \leqq 200,001.$
• $1 \leqq P_i \leqq 400,001.$
• $L_1,\ L_2,\ \cdots,\ L_N,\ R_1,\ R_2,\ \cdots,\ R_N,\ P_1,\ P_2,\ \cdots,\ P_M$ はすべて相異なる.
• $H_1,\ H_2,\ \cdots,\ H_N$ はすべて相異なる.

入出力の量が多いことに注意せよ. 例えば C++ を使用する場合 cin/cout ではなく scanf/printf 等の使用を推奨する.

入出力例

入力例 1

4
1 11 4
3 5 1
6 10 3
7 9 2
4
2
4
8
12

出力例1

1
2
3
0

入力例 2

12
5 37 8
8 23 3
4 18 10
24 27 5
9 13 11
10 25 1
14 30 9
22 29 7
26 39 12
1 28 4
12 17 2
3 11 6
15
2
36
38
15
35
34
6
31
20
7
32
19
21
16
33

出力例 2

1
1
1
4
1
1
2
1
2
2
1
2
2
4
1