AT_abc449_e [ABC449E] A += v

You are given integers $ N, M $ and an integer sequence $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ where each element is between $ 1 $ and $ M $ , inclusive. The following operation is performed $ 10^{100} $ times on this integer sequence $ A $ : - Let $ v $ be the integer between $ 1 $ and $ M $ , inclusive, with the fewest occurrences in $ A $ . If there are multiple such $ v $ , take the smallest among them. Then, append $ v $ to the end of $ A $ . You are given $ Q $ queries. The $ i $ -th query gives an integer $ X_i $ , so find the value of $ A_{X_i} $ after performing the operation $ 10^{100} $ times.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ Q $ $ X_1 $ $ X_2 $ $ \vdots $ $ X_Q $

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

### Sample Explanation 1 Initially, $ A=(1,1,2) $ . With each operation, $ A $ changes as follows: - First operation: The counts of $ 1, 2, 3 $ in $ A $ are $ 2, 1, 0 $ respectively, so $ v=3 $ . Append $ v $ to the end of $ A $ , giving $ A=(1,1,2,3) $ . - Second operation: The counts of $ 1, 2, 3 $ in $ A $ are $ 2, 1, 1 $ respectively, so $ v=2 $ . Append $ v $ to the end of $ A $ , giving $ A=(1,1,2,3,2) $ . - Third operation: The counts of $ 1, 2, 3 $ in $ A $ are $ 2, 2, 1 $ respectively, so $ v=3 $ . Append $ v $ to the end of $ A $ , giving $ A=(1,1,2,3,2,3) $ . - $ \vdots $ After performing the operation $ 10^{100} $ times, $ A $ becomes $ A=(1,1,2,3,2,3,1,2,\ldots) $ . ### Constraints - $ 1\le N,M\le 5\times 10^5 $ - $ 1\le A_i \le M $ - $ 1\le Q\le 2\times 10^5 $ - $ 1\le X_i \le 10^{18} $ - All input values are integers.