{"problem":{"name":"2D Solitaire","description":{"content":"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, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc070_d"},"statements":[{"statement_type":"Markdown","content":"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)$.  \nProcess $Q$ queries.\nFor each query, given a pair of integers $(X, Y)$, solve the following problem. (All queries are independent.)\n\n> There are $N + K + X$ cards labeled from $1$ to $N + K + X$.  \n> Each card has a pair of integers written on it. Specifically,\n> \n> *   For $1 \\leq i \\leq N+K$, card $i$ has $(A_i, B_i)$.\n> *   For $N + K + 1 \\leq i \\leq N + K + X$, card $i$ has $(i, Y)$.\n> \n> 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.  \n> You may perform the following sequence of operations any number of times, possibly zero.\n> \n> *   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:\n>     *   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$.\n> *   Then, remove card $j$ from the table and place card $i$ on the table (the removed card is no longer available).\n> \n> What is the minimum number of cards you can end up holding in your hand after performing these operations?\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq K \\leq 10$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq N + K$\n*   $1 \\leq B_i \\leq N + K$\n*   $A$ and $B$ are permutations of $(1, 2, \\dots, N+K)$.\n*   $1 \\leq X \\leq 10$\n*   $1 \\leq Y \\leq N + K$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format, where $\\mathrm{query}_i$ denotes the $i$\\-th query:\n\n$N$ $K$ $Q$\n$A_1$ $A_2$ $\\dots$ $A_{N+K}$\n$B_1$ $B_2$ $\\dots$ $B_{N+K}$\n$\\mathrm{query}_1$ \n$\\mathrm{query}_2$\n$\\vdots$\n$\\mathrm{query}_Q$\n\nEach query is given in the following format:\n\n$X$ $Y$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc070_d","tags":[],"sample_group":[["5 1 6\n1 2 3 4 6 5\n4 2 5 1 6 3\n2 1\n2 2\n2 3\n2 4\n2 5\n2 6","4\n3\n3\n3\n2\n1\n\nTaking the query $(X, Y) = (2, 2)$ (the second query) as an example:\nInitially, the cards in your hand and on the table are as follows:\n\n*   In your hand: $(1, 4), (2, 2), (3, 5), (4, 1), (6, 6)$\n*   On the table: $(5, 3), (7, 2), (8, 2)$\n\nYou can achieve holding three cards in your hand, which is the minimum, by performing the following operations:\n\n*   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.\n    *   In your hand: $(1, 4), (3, 5), (4, 1), (6, 6)$\n    *   On the table: $(2, 2), (7, 2), (8, 2)$\n*   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.\n    *   In your hand: $(1, 4), (3, 5), (6, 6)$\n    *   On the table: $(2, 2), (7, 2), (4, 1)$"],["10 2 10\n12 3 2 4 10 9 5 8 1 6 11 7\n3 7 2 6 10 9 1 11 5 8 4 12\n2 6\n3 3\n1 3\n1 7\n1 12\n3 4\n3 11\n2 1\n2 8\n1 5","4\n5\n5\n4\n2\n4\n1\n6\n3\n4"],["20 3 10\n18 16 5 12 21 23 14 1 19 17 3 15 13 22 7 4 2 8 9 20 6 11 10\n18 1 6 20 9 13 21 17 4 16 15 22 12 14 10 23 2 5 3 19 7 11 8\n1 11\n1 3\n3 19\n1 22\n2 15\n4 9\n3 16\n1 19\n5 21\n2 3","13\n15\n6\n11\n9\n13\n8\n12\n3\n15"]],"created_at":"2026-03-03 11:01:14"}}