CF1920D Array Repetition

Jayden 有一个初始为空的数组 $a$。他需要按顺序进行 $n$ 次操作，操作有两种类型： 1. Jayden 向数组 $a$ 的末尾添加一个整数 $x$（$1 \leq x \leq n$）。 2. Jayden 向数组 $a$ 的末尾添加 $x$ 份当前数组 $a$ 的拷贝。也就是说，数组 $a$ 变为 $[a, \underbrace{a, \ldots, a}_{x}]$。保证在进行此操作前，至少已经进行过一次第一种操作。 Jayden 有 $q$ 个询问。对于每个询问，你需要告诉他数组 $a$ 的第 $k$ 个元素。数组下标从 $1$ 开始。

每个测试包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。接下来是每组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$），分别表示操作次数和询问次数。 接下来的 $n$ 行，每行描述一次操作，包含两个整数 $b$ 和 $x$（$b \in \{1, 2\}$），$b$ 表示操作类型。如果 $b=1$，则 $x$（$1 \leq x \leq n$）为要添加到数组末尾的整数；如果 $b=2$，则 $x$（$1 \leq x \leq 10^9$）为要添加的数组 $a$ 的拷贝次数。 接下来一行包含 $q$ 个整数 $k_1, k_2, \ldots, k_q$（$1 \leq k_i \leq \min(10^{18}, c)$），表示每次询问的位置，其中 $c$ 为所有 $n$ 次操作后数组 $a$ 的长度。 保证所有测试用例中 $n$ 的总和与 $q$ 的总和不超过 $10^5$。

对于每组测试数据，输出 $q$ 个整数，分别为 Jayden 的每个询问的答案。

在第一个测试用例中： - 第一次操作后 $a = [1]$； - 第二次操作后 $a = [1, 2]$； - 第三次操作后 $a = [1, 2, 1, 2]$； - 第四次操作后 $a = [1, 2, 1, 2, 3]$； - 第五次操作后 $a = [1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3]$。 在第四个测试用例中，所有操作后 $a = [1, 2]$。 由 ChatGPT 4.1 翻译