Now the problem is much easier: we have N men stand in a line and labeled from 1 to N, for each round, we choose the first man, the k+1-th one, the 2*k+1-th one and so on, until the end of the line. These poor guys will be kicked out of the line and we will execute them immediately (may be head chop, or just shoot them, whatever), and then we start the next round with the remaining guys. The little difference between the Romans and us is, in our version of story, NO ONE SURVIVES. Your goal is to find out the death sequence of the man.
For example, we have N = 7 *ers, and we decided to kill every k=2 people in the line. At the beginning, the line looks like this:
1 2 3 4 5 6 7
after the first round, 1 3 5 7 will be executed, we have
2 4 6
and then, we will kill 2 6 in the second round. At last 4 will be executed. So, you need to output 1 3 5 7 2 6 4. Easy, right?
But the output maybe too large, we will give you Q queries, each one contains a number m, you need to tell me the m-th number in the death sequence.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N=;
int head[N];
int a[N];
struct Node
{
int to;
int next;
}node[N]; int main()
{
int T;
cin>>T;
while(T--)
{
int n,k,q;
scanf("%d%d%d",&n,&k,&q);
memset(head,,sizeof(head));
int tot=;
for(int i=;i<=n;i++)
{
if((i-)%k==) a[i]=;
else a[i]=a[i-(i-)/k-]+;
node[tot].to=i;
node[tot].next=head[a[i]];
head[a[i]]=tot++;
}
int cnt=n;
for(int i=tot-;i>=;i--)
{
for(int j=head[i];j;j=node[j].next)
{
a[cnt--]=node[j].to;
}
}
while(q--)
{
int x;
scanf("%d",&x);
printf("%d\n",a[x]);
}
}
return ;
}