Divine Array

题意翻译

### 题目描述 给定一个序列，一次转换是将一个数变成这个数在这个序列中出现的次数。 序列 $\{2,1,1,4,3,1,2\}$ 中，$2$ 出现 $2$ 次，$1$ 出现 $3$ 次，$3$ 和 $4$ 出现 $1$ 次，那么这个序列进行一次转换之后就变成了 $\{2,3,3,1,1,3,2\}$，同理，进行两次转换后是 $\{2,3,3,2,2,3,2\}$，进行三次转换后是 $\{4,3,3,4,4,3,4\}$。 有 $q$ 次询问，每次询问第 $x$ 个位置的元素经过 $k$ 次转换之后是什么。 ### 输入格式 第一行输入一个正整数 $t$ 表示数据组数。 对于每一组数据： - 第一行输入一个正整数 $n$ 表示序列长度。 - 第二行输入 $n$ 个正整数 $a_i$ 表示初始序列。 - 第三行输入一个正整数 $q$ 表示询问次数。 - 接下来 $q$ 行每行两个整数 $x,k$ 表示一次询问，含义见题目描述。 ### 输出格式 对于每一个询问输出一行一个正整数表示答案。 ### 数据范围 $1\le t\le1000,1\le\sum n\le2000,1\le a_i,x\le n,1\le\sum q\le10^5，0\le k\le10^9$。

题目描述

Black is gifted with a Divine array $ a $ consisting of $ n $ ( $ 1 \le n \le 2000 $ ) integers. Each position in $ a $ has an initial value. After shouting a curse over the array, it becomes angry and starts an unstoppable transformation. The transformation consists of infinite steps. Array $ a $ changes at the $ i $ -th step in the following way: for every position $ j $ , $ a_j $ becomes equal to the number of occurrences of $ a_j $ in $ a $ before starting this step. Here is an example to help you understand the process better: Initial array: $ 2 $ $ 1 $ $ 1 $ $ 4 $ $ 3 $ $ 1 $ $ 2 $ After the $ 1 $ -st step: $ 2 $ $ 3 $ $ 3 $ $ 1 $ $ 1 $ $ 3 $ $ 2 $ After the $ 2 $ -nd step: $ 2 $ $ 3 $ $ 3 $ $ 2 $ $ 2 $ $ 3 $ $ 2 $ After the $ 3 $ -rd step: $ 4 $ $ 3 $ $ 3 $ $ 4 $ $ 4 $ $ 3 $ $ 4 $ ......In the initial array, we had two $ 2 $ -s, three $ 1 $ -s, only one $ 4 $ and only one $ 3 $ , so after the first step, each element became equal to the number of its occurrences in the initial array: all twos changed to $ 2 $ , all ones changed to $ 3 $ , four changed to $ 1 $ and three changed to $ 1 $ . The transformation steps continue forever. You have to process $ q $ queries: in each query, Black is curious to know the value of $ a_x $ after the $ k $ -th step of transformation.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). Description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 2000 $ ) — the size of the array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ) — the initial values of array $ a $ . The third line of each test case contains a single integer $ q $ ( $ 1 \le q \le 100\,000 $ ) — the number of queries. Next $ q $ lines contain the information about queries — one query per line. The $ i $ -th line contains two integers $ x_i $ and $ k_i $ ( $ 1 \le x_i \le n $ ; $ 0 \le k_i \le 10^9 $ ), meaning that Black is asking for the value of $ a_{x_i} $ after the $ k_i $ -th step of transformation. $ k_i = 0 $ means that Black is interested in values of the initial array. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 2000 $ and the sum of $ q $ over all test cases doesn't exceed $ 100\,000 $ .

输出格式

For each test case, print $ q $ answers. The $ i $ -th of them should be the value of $ a_{x_i} $ after the $ k_i $ -th step of transformation. It can be shown that the answer to each query is unique.

输入输出样例

输入样例 #1

2
7
2 1 1 4 3 1 2
4
3 0
1 1
2 2
6 1
2
1 1
2
1 0
2 1000000000

输出样例 #1

1
2
3
3
1
2

说明

The first test case was described ih the statement. It can be seen that: 1. $ k_1 = 0 $ (initial array): $ a_3 = 1 $ ; 2. $ k_2 = 1 $ (after the $ 1 $ -st step): $ a_1 = 2 $ ; 3. $ k_3 = 2 $ (after the $ 2 $ -nd step): $ a_2 = 3 $ ; 4. $ k_4 = 1 $ (after the $ 1 $ -st step): $ a_6 = 3 $ . For the second test case, Initial array: $ 1 $ $ 1 $ After the $ 1 $ -st step: $ 2 $ $ 2 $ After the $ 2 $ -nd step: $ 2 $ $ 2 $ ......It can be seen that: 1. $ k_1 = 0 $ (initial array): $ a_1 = 1 $ ; 2. $ k_2 = 1000000000 $ : $ a_2 = 2 $ ;