005 - パスタの茹で具合

時間制限 1 秒 / メモリ制限 64 MB / 得点 6 / x 8 /


TLE
1sec
MLE
64MB
得点
6

問題

パスタ博士であるPCK君は、毎晩パスタを調理して食べている。調理に使用するパスタは同じ製品で、茹で時間が短い順に「茹で足りない」「ちょうど良い」「茹ですぎ」のように茹で具合が変化する。パスタの茹で具合は茹で時間だけで決まるので、茹で時間が同じなら同じ茹で具合になる。

PCK君は様々な時間でパスタを調理したときの茹で具合の記録を$N$ 日間取っており、さらに$M$ 日間、様々な茹で時間でパスタを調理する予定である。

パスタの茹で具合の記録を取った日数、それぞれの日のパスタの茹で時間と茹で具合、これからパスタを調理する日数、それぞれのパスタの茹で時間が与えられたとき、それぞれのパスタが「茹で足りない」「ちょうど良い」「茹ですぎ」または「判断できない」のどれであるかを判定するプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$a_1 s_1$
$a_2 s_2$
:
$a_N s_N$
$M$
$b_1$
$b_2$
:
$b_M$

1行目に、記録を取った日数$N(1 \leq N \leq 100)$が与えられられる。続く$N$行に、$i$日目の調理から得られた茹で時間$a_i(1 \leq a_i \leq 1,000,000,000)$と茹で具合$s_i(0 \leq s_i \leq 2)$が整数で与えられる。$s_i$はパスタを$a_i$分間茹でたときの具合であり、0のとき「茹で足りない」、1のとき「ちょうど良い」、2のとき「茹ですぎ」を表す。ただし、$i≠j$ならば$a_i≠a_j$、かつ、$s_i \lt s_j$ならば$a_i \lt a_j$とする。

続く1行に、これから調理する日数$M(1 \leq M \leq 100)$が与えられる。続く$M$行に、それぞれの日に調理するパスタの茹で時間$b_i(1 \leq b_i \leq 1,000,000,000)$が整数で与えられる。

出力

パスタを$b_i$分間茹でた時の茹で具合を$i$行目に出力する。「茹で足りない」「ちょうど良い」「茹ですぎ」または「判断できない」をそれぞれ0,1,2,-1で表すものとする。

入出力例

入力例1

4
9 2
3 0
7 1
5 1
5
12
2
9
6
5

出力例1

2
0
2
1
1

入力例2

5
4 1
6 2
1 0
8 2
3 1
4
4
7
10
2

出力例2

1
2
2
-1

パスタを7分間茹でた場合と10分間茹でた場合の茹で具合は、6分間茹でた場合の茹で具合から「茹ですぎ」と判断できる。いっぽう、1分間茹でた場合と3分間茹でた場合の茹で具合が異なることから、パスタを2分間茹でた場合の茹で具合は判断できない。

入力例3

2
1 0
3 2
1
2

出力例3

-1

茹で時間が1分と3分の場合の茹で具合がそれぞれ「茹で足りない」と「茹ですぎ」であることが分かっている。このとき、ちょうど良い茹で具合になる茹で時間の範囲は、1分過ぎから2分未満まで、1分過ぎから3分未満まで、2分過ぎから3分未満まで、の3つの場合があり得る。これらの場合で、2分での茹で具合はそれぞれ「茹ですぎ」、「ちょうど良い」、「茹で足りない」となる。このため、パスタを2分間茹でた場合の茹で具合は判断できない。