{"raw_statement":[{"iden":"statement","content":"In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize to manage a cache of information stored on the computer. Caching improves performance by keeping recent or often-used data items in memory locations that are faster or computationally cheaper to access than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for the new ones.\n\nOne of the most famous cache algorithms is called the _Least Recently Used_ (LRU) algorithm. In LRU, items in the cache are typically maintained with a linked list. When an item is accessed, it is removed from the linked list (if present), and then inserted to the front of the list. The front of the linked list is the _Most Recently Used_ item. Because used items are continually being moved to the front of the linked list, the least used ones naturally end up at the back of the list. When there's not enough room in the cache, the item at the back of the linked list is discarded.\n\nIn this problem, each item in the cache is given a unique positive integer identifier for convenience. For example, let's consider the access sequence {4, 3, 4, 2, 3, 1, 4} and assume that the capacity of the cache is 3. The following table shows the content of the linked list.\n\nNow, you want to do some memory optimization for your program. To that end, you are going to run some experiments. Assume that the LRU algorithm is used to manage the cache. The access sequence of your program is known and fixed, and you want to run $q$ experiments about the cache. In the $i$-th $(1 <= i <= q)$ experiment, the capacity of the cache is set to $m_i$ and you have a linked list $x_i$. You want to find out if at some point during the execution of your program, the linked list maintained by the LRU algorithm is exactly the same as $x_i$.\n\nJust before you start running your program to experiment, one of your friends challenged you to find out the results without actually running the experiment $q$ times. He asks you to write a simple program to find out the answer, can you do it?\n\nThe input contains multiple cases. The first line of the input contains a single positive integer $T$, the number of cases.\n\nFor each case, the first line of the input contains two integers $n, q$ ($1 <= n <= 5 thin 000, 1 <= q <= 2 thin 000$), the length of the access sequence and the number of experiments. The second line contains $n$ integers $a_1, a_2, \\\\dots, a_n$ ($1 <= i <= n, 1 <= a_i <= n$), where the $i$-th integer denotes the identifier of the item accessed in the $i$-th operation.\n\nThe following $q$ lines each describes an experiment. The $i$-th $(1 <= i <= q)$ line contains an integer $m_i$ ($1 <= m_i <= n$), the capacity of the cache, followed by $m_i$ integers $x_{i , 1}, x_{i , 2}, \\\\dots, x_{i , m_i}$ ($1 <= j <= m_i, 0 <= x_{i , j} <= n$), where the $j$-th integer denotes the identifier of the $j$-th item in the linked list $x_i$. Note that the number of items in $x_i$ may be less than $m_i$. Let $L_i$ be the length of $x_i$, then the last $m_i -L_i$ integers in the input will be equal to $0$, those zeroes should be ignored, while the other integers will be positive.\n\nIt's guaranteed that the sum of $n$ over all cases does not exceed $20 thin 000$, the sum of $q$ over all cases does not exceed $20 thin 000$ and the sum of $m_i$ over all cases does not exceed $2 dot.op 10^6$.\n\nFor each case, print $q$ lines, where the $i$-th line describes the result of the $i$-th experiment. If at some point, the linked list maintained by the LRU algorithm is equal to the given list $x_i$, print the string \"_Yes_\" (without quotes). Otherwise, print the string \"_No_\" (without quotes).\n\n"},{"iden":"input","content":"The input contains multiple cases. The first line of the input contains a single positive integer $T$, the number of cases.For each case, the first line of the input contains two integers $n, q$ ($1 <= n <= 5 thin 000, 1 <= q <= 2 thin 000$), the length of the access sequence and the number of experiments. The second line contains $n$ integers $a_1, a_2, \\\\dots, a_n$ ($1 <= i <= n, 1 <= a_i <= n$), where the $i$-th integer denotes the identifier of the item accessed in the $i$-th operation.The following $q$ lines each describes an experiment. The $i$-th $(1 <= i <= q)$ line contains an integer $m_i$ ($1 <= m_i <= n$), the capacity of the cache, followed by $m_i$ integers $x_{i , 1}, x_{i , 2}, \\\\dots, x_{i , m_i}$ ($1 <= j <= m_i, 0 <= x_{i , j} <= n$), where the $j$-th integer denotes the identifier of the $j$-th item in the linked list $x_i$. Note that the number of items in $x_i$ may be less than $m_i$. Let $L_i$ be the length of $x_i$, then the last $m_i -L_i$ integers in the input will be equal to $0$, those zeroes should be ignored, while the other integers will be positive.It's guaranteed that the sum of $n$ over all cases does not exceed $20 thin 000$, the sum of $q$ over all cases does not exceed $20 thin 000$ and the sum of $m_i$ over all cases does not exceed $2 dot.op 10^6$."},{"iden":"output","content":"For each case, print $q$ lines, where the $i$-th line describes the result of the $i$-th experiment. If at some point, the linked list maintained by the LRU algorithm is equal to the given list $x_i$, print the string \"_Yes_\" (without quotes). Otherwise, print the string \"_No_\" (without quotes)."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each case:  \n- Let $ n \\in \\mathbb{Z}^+ $ be the length of the access sequence.  \n- Let $ A = (a_1, a_2, \\dots, a_n) $ be the access sequence, where $ a_i \\in \\{1, 2, \\dots, n\\} $.  \n- Let $ q \\in \\mathbb{Z}^+ $ be the number of experiments.  \n- For each experiment $ i \\in \\{1, \\dots, q\\} $:  \n  - Let $ m_i \\in \\mathbb{Z}^+ $ be the cache capacity.  \n  - Let $ X_i = (x_{i,1}, x_{i,2}, \\dots, x_{i,L_i}) $ be the target linked list state, where $ L_i \\leq m_i $, $ x_{i,j} \\in \\mathbb{Z}^+ $ for $ j \\in \\{1, \\dots, L_i\\} $, and $ x_{i,j} = 0 $ for $ j > L_i $ (ignored).  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unknown} $, but total $ \\sum n \\leq 20{,}000 $, $ \\sum q \\leq 20{,}000 $, $ \\sum m_i \\leq 2 \\times 10^6 $.  \n2. $ 1 \\leq n \\leq 5{,}000 $, $ 1 \\leq q \\leq 2{,}000 $ per case.  \n3. $ 1 \\leq a_i \\leq n $, $ 1 \\leq m_i \\leq n $, $ 0 \\leq x_{i,j} \\leq n $, with $ x_{i,j} = 0 $ for padding.  \n4. Non-zero elements in $ X_i $ are distinct and positive.  \n\n**Objective**  \nFor each experiment $ i $, simulate the LRU cache with capacity $ m_i $ on sequence $ A $, maintaining a linked list ordered from most recently used (front) to least recently used (back).  \nAt each access step $ k \\in \\{1, \\dots, n\\} $, update the list as follows:  \n- If $ a_k $ is in the list, remove it and insert it at the front.  \n- Else, if the list has fewer than $ m_i $ elements, append $ a_k $ at the front.  \n- Else, remove the last element, then insert $ a_k $ at the front.  \n\nDetermine whether, at any step $ k $, the current list equals $ X_i $ (ignoring trailing zeros).  \nOutput \"Yes\" if such a state occurs; otherwise, output \"No\".","simple_statement":"Given a sequence of cache accesses and a fixed LRU cache policy, for each query with a cache capacity and a target linked list, determine if the LRU cache ever matches that exact list during the access sequence.","has_page_source":false}