← 返回题目列表

Codeforces · 1602/B

B. 神阵

中文机器翻译题面 查看原题

黑方拥有一个由 $$$n$$$ ($$$1 \le n \le 2000$$$) 整数组成的神圣数组 $$$a$$$。 $$$a$$$ 中的每个位置都有一个初始值。对着阵法大喊一声咒骂后,它变得愤怒,开始了不可阻挡的变身。

转换由无限步骤组成。数组 $$$a$$$ 在第 $$$i$$$ 步骤发生以下变化:对于每个位置 $$$j$$$,$$$a_j$$$ 变得等于开始此步骤之前 $$$a_j$$$ 在 $$$a$$$ 中出现的次数。

下面是一个示例,可以帮助您更好地理解该过程:

初始数组:$$$2$$$ $$$1$$$ $$$1$$$ $$$4$$$ $$$3$$$ $$$1$$$ $$$2$$$$$$1$$$-st 步骤之后:$$$2$$$ $$$3$$$ $$$3$$$ $$$1$$$ $$$1$$$ $$$3$$$ $$$2$$$在$$$2$$$-第一个步骤之后:$$$2$$$ $$$3$$$ $$$3$$$ $$$2$$$ $$$2$$$ $$$3$$$ $$$2$$$在$$$3$$$-第一个步骤之后:$$$4$$$ $$$3$$$ $$$3$$$ $$$4$$$ $$$4$$$$$$3$$$$$$4$$$......

在初始数组中,我们有两个 $$$2$$$-、三个 $$$1$$$-、只有一个 $$$4$$$ 和一个 $$$3$$$,因此在第一步之后,每个元素都等于其在初始数组中出现的次数:所有 2 都更改为 $$$2$$$,所有 1 更改为 $$$3$$$,4 更改为 $$$1$$$三个改为$$$1$$$。

转变步骤将永远持续下去。

你必须处理 $$$q$$$ 查询:在每个查询中,Black 很想知道第 $$$k$$$ 转换步骤之后 $$$a_x$$$ 的值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的初始值。

每个测试用例的第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 100\,000$$$) — 查询数量。

接下来的 $$$q$$$ 行包含有关查询的信息 - 每行一个查询。第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$k_i$$$ ($$$1 \le x_i \le n$$$; $$$0 \le k_i \le 10^9$$$),这意味着黑棋要求在第 $$$k_i$$$ 变换步骤之后 $$$a_{x_i}$$$ 的值。 $$$k_i = 0$$$ 表示黑方对初始数组的值感兴趣。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$,所有测试用例的 $$$q$$$ 总和不超过 $$$100\,000$$$。

输出

对于每个测试用例,打印 $$$q$$$ 答案。其中第 $$$i$$$ 应该是第 $$$k_i$$$ 步骤转换后 $$$a_{x_i}$$$ 的值。可以证明每个查询的答案都是唯一的。

示例

输入 #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

注意

第一个测试用例在声明中进行了描述。可见:

1. $$$k_1 = 0$$$(初始数组):$$$a_3 = 1$$$;
2. $$$k_2 = 1$$$(在 $$$1$$$-st 步骤之后):$$$a_1 = 2$$$;
3. $$$k_3 = 2$$$(在$$$2$$$-nd步骤之后):$$$a_2 = 3$$$;
4. $$$k_4 = 1$$$(在 $$$1$$$-st 步骤之后):$$$a_6 = 3$$$。

对于第二个测试用例,初始数组:$$$1$$$ $$$1$$$$$$1$$$-st 步骤之后:$$$2$$$ $$$2$$$$$$2$$$-nd 步骤之后:$$$2$$$ $$$2$$$......

可以看出:

1. $$$k_1 = 0$$$(初始数组):$$$a_1 = 1$$$;
2. $$$k_2 = 1000000000$$$: $$$a_2 = 2$$$;