问题 J: ht的生日party

问题 J: ht的生日party

时间限制: 1 Sec  内存限制: 128 MB
提交: 138  解决: 14
[提交] [状态] [讨论版] [命题人:]
题目描述

 即使tmk上了大学,tmk还是十分怀念以前的高中生活还有以前的小伙伴们。

       Tmk还记得在高考前几天,tmk和他的小伙伴们参加了ht的生日party。在某个时间点,需要选出一个唱歌的人,于是tmk提议说不如我们来玩一次约瑟夫问题吧。

       我们有n个人排成一列,首先从头到尾报数1,2,3…..n,报到m的倍数的人出列,接下来从尾到头报数,报到m的倍数的人出列。直到人数小于m,这时再报一次数,报到1的人就被选出来唱歌。

       现在问谁是出来唱歌的人

 

输入

首先第一个数TT<=10,表示数据组数。

每组数据,第一行有两个数,nm1<=n<=10000,1<m<=1000000),分别表示询问数和题目中的m

接下来有n行,每行一个数x(1<x<=1000000),表示一个询问,即问x个人排成一列,原编号为多少的人会被选出来唱歌。

 

输出

对于每组数据,输出n行,每行一个整数,第i行的整数表示第i个询问的答案

 

样例输入 Copy
2
2 3
1
6
2 4
1
6
样例输出 Copy
1
4
1
5