AT_agc070_d [AGC070D] 2D Solitaire

正整数 $ N, K $ および $ (1, 2, \dots, N+K) $ の順列 $ A=(A_1,A_2,\dots,A_{N+K}),B=(B_1,B_2,\dots,B_{N+K}) $ が与えられます。 $ Q $ 個のクエリが与えられるので処理してください。 各クエリでは整数の組 $ (X, Y) $ が与えられるので、次の問題を解いてください。(全てのクエリは独立です。) > $ 1 $ から $ N + K + X $ までの番号がついた $ N + K + X $ 枚のカードがあります。 > 各カードには整数の組が書かれていて、カード $ i $ には > > - $ 1 \leq i \leq N+K $ の時、 $ (A_i, B_i) $ > - $ N + K + 1 \leq i \leq N + K + X $ の時、 $ (i, Y) $ > > が書かれています。 > > 今、あなたはカード $ 1 $ からカード $ N $ までの $ N $ 枚のカードを持っています。また、場にカード $ N+1 $ からカード $ N+K+X $ までの $ K+X $ 枚のカードが場に置かれています。 > あなたは次の一連の操作を $ 0 $ 回以上自由な回数行うことが出来ます。 > > - まず、持っているカードと場に置かれているカードを $ 1 $ 枚ずつ選び、それぞれカード $ i $ 、カード $ j $ とする。ただし、選んだカードは次の条件を満たす必要がある。 > - カード $ i $ に書かれている整数の組を $ (a_i, b_i) $ 、カード $ j $ に書かれている整数の組を $ (a_j, b_j) $ とした時、 $ a_i \lt a_j $ かつ $ b_i \lt b_j $ が成り立つ必要がある。 > - そして、カード $ j $ を場から取り除き、かわりにカード $ i $ を場に置く。(取り除かれたカードはその後選択できない。) > > 操作によって持っているカードの枚数を最小で何枚にすることができますか？

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{query}_i $ は $ i $ 番目のクエリを意味する。 > $ N $ $ K $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_{N+K} $ $ B_1 $ $ B_2 $ $ \dots $ $ B_{N+K} $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ X $ $ Y $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリへの答えを出力せよ。

### Sample Explanation 1 $ 2 $ 番目のクエリ、すなわち $ (X, Y) = (2, 2) $ の場合を例に挙げて説明します。 はじめ、持っているカードと場に出ているカードを列挙すると次のようになります。 - 持っているカード : $ (1, 4), (2, 2), (3, 5), (4, 1), (6, 6) $ - 場に出ているカード : $ (5, 3), (7, 2), (8, 2) $ この時、次のように操作を行うことで持っているカードの枚数を $ 3 $ 枚にすることができて、これが最小です。 - 持っているカードとして $ (2, 2) $ が書かれたカード $ 2 $ を、場に出ているカードとして $ (5, 3) $ が書かれたカード $ 6 $ を選ぶ。カード $ 6 $ を場から取り除き、カード $ 2 $ を場に置く。取り除かれていないカードの状況は次のようになる。 - 持っているカード : $ (1, 4), (3, 5), (4, 1), (6, 6) $ - 場に出ているカード : $ (2, 2), (7, 2), (8, 2) $ - 持っているカードとして $ (4, 1) $ が書かれたカード $ 4 $ を、場に出ているカードとして $ (8, 2) $ が書かれたカード $ 8 $ を選ぶ。カード $ 8 $ を場から取り除き、カード $ 4 $ を場に置く。取り除かれていないカードの状況は次のようになる。 - 持っているカード : $ (1, 4), (3, 5), (6, 6) $ - 場に出ているカード : $ (2, 2), (7, 2), (4, 1) $ ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq K \leq 10 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq N + K $ - $ 1 \leq B_i \leq N + K $ - $ A, B $ は $ (1, 2, \dots, N+K) $ の順列 - $ 1 \leq X \leq 10 $ - $ 1 \leq Y \leq N + K $ - 入力される値は全て整数