解题思路

设第 $i$ 名亲戚的到访时刻为等差序列 $\{a_i, 2a_i, 3a_i,\dots\}$。把所有亲戚的到访时刻合并并按“时间升序、同一秒按编号升序”排序，要求第 $k$ 次到访对应的亲戚编号。

核心做法是参数二分（Binary Search on Answer）+ 计数函数：

1. 定义计数函数 对于任意时刻 $t$，统计截至 $t$ 秒内到访的总次数：

   $$$$

题目内容

阿宅的寒假共有 $T$ 天；每天有 $n$ 名亲戚来他家做客；每到饭点时，所有亲戚会来叫在房间里编程的阿宅吃饭；第 $i$ 名亲戚每隔 $a_i$ 秒会来一次，首次来叫的时间为 $a_i$ 秒（即，第 $i$ 名亲戚的到访时间为 $a_i, 2a_i, 3a_i, …$）。

阿宅想知道，每一天第 $k$ 次来叫他的亲戚编号；若同一秒内有多名亲戚同时来叫，则编号较小者优先。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 $T (1 ≤ T ≤ 30)$，表示寒假天数；

此后对每天数据，描述如下：

• 在一行上输入两个整数 $n$ 和 $k (1 ≤ n ≤ 10^5; 1 ≤ k ≤ 10^9)$，分别表示亲戚人数和要查询的第 $k$ 次。
• 在一行输入 $n$ 个整数 $a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9)$，表示第 $i$ 名亲戚来叫的时间间隔。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 × 10^5$ 。

输出描述

对于每一组测试数据，输出一行。输出一个整数，表示对应天第 $k$ 次来叫吃饭的亲戚编号。

样例1

输入

6
3 1
1 2 3
3 2
1 2 3
3 3
1 2 3
3 4
1 2 3
3 5
1 2 3
3 6
5 7 11

输出

1
1
2
1
3
1

说明

对于第一、二、三、四、五组测试数据，每一秒的到访序列依次为：

• 第一秒，仅有亲戚 $1$ 来叫；
• 第二秒，亲戚 $1$ 和 $2$ 来叫；
• 第三秒，亲戚 $1$ 和 $3$ 来叫。