AT_agc070_d [AGC070D] 2D Solitaire

You are given positive integers $ N $ and $ K $ , and two permutations $ A = (A_1, A_2, \dots, A_{N+K}) $ and $ B = (B_1, B_2, \dots, B_{N+K}) $ of $ (1, 2, \dots, N+K) $ . Process $ Q $ queries. For each query, given a pair of integers $ (X, Y) $ , solve the following problem. (All queries are independent.) > There are $ N + K + X $ cards labeled from $ 1 $ to $ N + K + X $ . > Each card has a pair of integers written on it. Specifically, > > - For $ 1 \leq i \leq N+K $ , card $ i $ has $ (A_i, B_i) $ . > - For $ N + K + 1 \leq i \leq N + K + X $ , card $ i $ has $ (i, Y) $ . > > At the beginning, you have the $ N $ cards $ 1 $ to $ N $ in your hand, and the $ K + X $ cards from $ N+1 $ to $ N + K + X $ are on the table. > You may perform the following sequence of operations any number of times, possibly zero. > > - First, choose one card from your hand and one card from the table, calling them card $ i $ and card $ j $ . Here, the following condition must hold: > - Let $ (a_i, b_i) $ be the pair of integers written on card $ i $ , and $ (a_j, b_j) $ be the pair on card $ j $ . You must have $ a_i < a_j $ and $ b_i < b_j $ . > - Then, remove card $ j $ from the table and place card $ i $ on the table (the removed card is no longer available). > > What is the minimum number of cards you can end up holding in your hand after performing these operations?

The input is given from Standard Input in the following format, where $ \mathrm{query}_i $ denotes the $ i $ -th query: > $ 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 $ Each query is given in the following format: > $ X $ $ Y $

Print $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 Taking the query $ (X, Y) = (2, 2) $ (the second query) as an example: Initially, the cards in your hand and on the table are as follows: - In your hand: $ (1, 4), (2, 2), (3, 5), (4, 1), (6, 6) $ - On the table: $ (5, 3), (7, 2), (8, 2) $ You can achieve holding three cards in your hand, which is the minimum, by performing the following operations: - Choose card $ 2 $ in your hand with $ (2, 2) $ and card $ 6 $ on the table with $ (5, 3) $ . Remove card $ 6 $ from the table and place card $ 2 $ on the table. Now, the following cards are remaining. - In your hand: $ (1, 4), (3, 5), (4, 1), (6, 6) $ - On the table: $ (2, 2), (7, 2), (8, 2) $ - Choose card $ 4 $ in your hand with $ (4, 1) $ and card $ 8 $ on the table with $ (8, 2) $ . Remove card $ 8 $ from the table and place card $ 4 $ on the table. Now, the following cards are remaining. - In your hand: $ (1, 4), (3, 5), (6, 6) $ - On the table: $ (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 $ and $ B $ are permutations of $ (1, 2, \dots, N+K) $ . - $ 1 \leq X \leq 10 $ - $ 1 \leq Y \leq N + K $ - All input values are integers.