AT_abc389_f [ABC389F] Rated Range

高橋君はAtCoderのコンテストに $ N $ 回参加しようとしています。 $ i $ 回目 $ (1 \leq i \leq N) $ のコンテストでは、レーティングが $ L_i $ 以上 $ R_i $ 以下である場合、レーティングが $ 1 $ 増加します。 以下の形式で与えられる $ Q $ 個のクエリに答えてください。 - 整数 $ X $ が与えられる。高橋君の最初のレーティングが $ X $ であった場合、 $ N $ 回のコンテストを終えた後のレーティングを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $ $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ ただし、 $ \text{query}_i $ は $ i $ 個目のクエリを表し、以下の形式である。 > $ X $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 個目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 個目のクエリでは以下のようにコンテストごとにレーティングが変化します。 - $ 1 $ 回目のコンテストではレーティングが $ 1 $ 以上 $ 5 $ 以下のため、レーティングが $ 1 $ 増加し $ 4 $ になります。 - $ 2 $ 回目のコンテストではレーティングが $ 1 $ 以上 $ 3 $ 以下でないため、レーティングが増加せず $ 4 $ のままです。 - $ 3 $ 回目のコンテストではレーティングが $ 3 $ 以上 $ 6 $ 以下のため、レーティングが $ 1 $ 増加し $ 5 $ になります。 - $ 4 $ 回目のコンテストではレーティングが $ 2 $ 以上 $ 4 $ 以下でないため、レーティングが増加せず $ 5 $ のままです。 - $ 5 $ 回目のコンテストではレーティングが $ 4 $ 以上 $ 7 $ 以下のため、レーティングが $ 1 $ 増加し $ 6 $ になります。 $ 2 $ 個目のクエリでは $ 1,2,3,5 $ 回目のコンテストでレーティングが $ 1 $ 増加するため、レーティングは $ 6 $ になります。 $ 3 $ 個目のクエリでは $ 1,3,5 $ 回目のコンテストでレーティングが $ 1 $ 増加するため、レーティングは $ 8 $ になります。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq L_i \leq R_i \leq 5 \times 10^5 $ $ (1 \leq i \leq N) $ - $ 1 \leq Q \leq 3 \times 10^5 $ - 各クエリについて $ 1 \leq X \leq 5 \times 10^5 $ - 入力は全て整数