問題
レストラン$K$では$N$個のメニューを提供しており、
$i$個目の料理のカロリーは$A_i$,栄養価は$B_i$,おいしさが$C_i$です。
このレストランに$M$人の客が訪れ、それぞれが自分の好みに合ったメニューを探しています。
客$j$は以下の3つの条件をすべて満たすメニューを注文することができます。
・料理のカロリーが$C1_j$以上$C2_j$以下である
・料理の栄養価が$F1_j$以上$F2_j$以下である
・料理のおいしさが$D_j$以上である
$N$個の料理の情報と$M$人の客が求める情報が与えられるので、すべての客に対し、注文可能な料理の種類を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ : $A_N$ $B_N$ $C_N$ $M$ $C1_1$ $C2_1$ $F1_1$ $F2_1$ $D_1$ $C1_2$ $C2_2$ $F1_2$ $F2_2$ $D_2$ : $C1_M$ $C2_M$ $F1_M$ $F2_M$ $D_M$
出力
$i = 1,2,3...M$について、客$i$が注文可能な料理の数を改行区切りで出力してください。
また、最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 4000$
- $1 \leq M \leq 10^5$
- $0 \leq A_i,B_i,C_i \leq 10^9$
- $0 \leq C1_j < C2_j \leq 10^9$
- $0 \leq F1_j < F2_j \leq 10^9$
- $0 \leq D_j \leq 10^9$
入出力例
入力例1
2 950 20 50 1200 50 80 5 800 1000 10 40 40 750 950 10 20 50 800 1000 10 40 60 1000 3000 10 60 0 950 1200 20 50 50
出力例1
1 1 0 1 2
客$1$は条件を満たす料理$1$を注文できます。料理$2$はカロリーと栄養価の条件にあてはまりません。
客$2$は条件を満たす料理$1$を注文できます。料理$2$はカロリーと栄養価の条件にあてはまりません。
客$3$は条件を満たす料理がないため注文できません。料理$1$はおいしさの条件に、料理$2$はカロリーと栄養価の条件にあてはまりません。
客$4$は条件を満たす料理$2$を注文できます。料理$1$はカロリーの条件にあてはまりません。
客$5$は条件を満たす料理$1$と料理$2$を注文できます。
入力例2
10 50 60 100 20 30 80 80 10 80 90 90 70 10 100 70 30 50 60 70 70 50 40 20 40 60 80 40 100 40 20 5 20 80 10 70 60 0 100 0 100 0 50 50 60 60 100 10 100 10 100 75 90 90 90 90 10
出力例2
4 10 1 3 1
入力例3
8 1 1 10 1000000000 1000000000 1000 50 50 100 50 50 200 999999999 1000000000 1000 1 2 20 2 1 30 2 2 40 5 0 1000000000 0 1000000000 0 50 50 50 50 150 0 100 0 100 100 1 1 1000000000 1000000000 100 1 1 1 1 500
出力例3
8 1 2 0 0
入力例4
1 1000000000 0 0 3 0 100 0 100 100 999999999 1000000000 0 10 0 0 1000000000 1 2 1
出力例4
0 1 0
余談ですが、$10^9$[cal]はだいたいTNT1キロトン相当らしいです。