#agc013f. [agc013_f]Two Faced Cards

[agc013_f]Two Faced Cards

問題文

表と裏が区別できるカードが NN 枚あります。 このうち ii 枚目のカードには、表に整数 AiA_i が、裏に整数 BiB_i が書かれています。 これらのカードの山を XX と呼びます。 また、別のカードが N+1N+1 枚あります。 このうち ii 番目のカードには、表に整数 CiC_i が書かれています。 裏には何も書かれていません。 これらのカードの山を YY と呼びます。

あなたはこれから、QQ 回ゲームを行います。 すべてのゲームは独立に行われます。 ii 回目のゲームでは、表と裏の区別できる新しいカードが渡されます。 このカードの表には整数 DiD_i が、裏には整数 EiE_i が書かれています。 これと XX を合わせて、N+1N+1 枚のカードの山 ZZ を作ります。 その後、ZZ のカードと YY のカード 11 枚ずつからなるペアを、N+1N+1 個作ります。 どのカードも、必ずいずれか一つのペアに属している必要があります。 この時、ZZ のカードそれぞれについて、「使用する面」を決めます。 その際、どのペアについても、

ZZ のカードの「使用する面」に書かれている整数 leq\\leq YY のカードに書かれている整数

が成り立っている必要があります。 どのようにペアを作って「使用する面」を決めてもこの条件を満たすことができない場合、 ゲームのスコアは \-1\-1 です。 そうでない場合ゲームのスコアは、「使用する面」が表である ZZ のカードの枚数です。

すべてのゲームについて、ゲームのスコアの最大値を求めてください。

制約

  • 入力は全て整数である
  • 1leqNleq1051 \\leq N \\leq 10^5
  • 1leqQleq1051 \\leq Q \\leq 10^5
  • 1leqAi,Bi,Ci,Di,Eileq1091 \\leq A_i ,B_i ,C_i ,D_i ,E_i \\leq 10^9

入力

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

NN A1A_1 B1B_1 A2A_2 B2B_2 :: ANA_N BNB_N C1C_1 C2C_2 .... CN+1C_{N+1} QQ D1D_1 E1E_1 D2D_2 E2E_2 :: DQD_Q EQE_Q

出力

それぞれのゲームについて、そのゲームのスコアの最大値を 11 行に出力せよ。


入力例 1

3
4 1
5 3
3 1
1 2 3 4
3
5 4
4 3
2 3

出力例 1

0
1
2

例えば 33 回目のゲームでは、ZZ のカードは、(4,1),(5,3),(3,1),(2,3)(4,1),(5,3),(3,1),(2,3) となります。 これらのカードの使用する面をそれぞれ、表、裏、裏、表、として、YY のカードの 4,3,1,24,3,1,2 番目のものとそれぞれペアにすれば、 条件を満たし、スコアが 22 になります。スコアを 33 以上にはできないので、22 が答えになります。


入力例 2

5
7 1
9 7
13 13
11 8
12 9
16 7 8 6 9 11
7
6 11
7 10
9 3
12 9
18 16
8 9
10 15

出力例 2

4
3
3
1
-1
3
2

入力例 3

9
89 67
37 14
6 1
42 25
61 22
23 1
63 60
93 62
14 2
67 96 26 17 1 62 56 92 13 38
11
93 97
17 93
61 57
88 62
98 29
49 1
5 1
1 77
34 1
63 27
22 66

出力例 3

7
9
8
7
7
9
9
10
9
7
9