时间限制	内存限制
`1000 ms`	`65536 KB`

# 题目描述

在 Baymax 的糖果王国里，有 $n$ 个糖果，每个糖果都有一个不同的味道。王国的官员 BBetula 和 CBetula 是糖果品鉴专家。他们喜欢进行一种特殊的游戏，游戏规则如下：

将 $n$ 个糖果摆成一个圆圈，每个糖果逆时针编号为 $1∼n$ 。
游戏将进行若干轮次，对于每个轮次，官员 BBetula 将从上一轮次结束时的位置开始 逆时针 数 $k$ 个糖果，官员 CCBetula 将从上一轮次结束时的位置开始 顺时针 数 $m$ 个糖果，且两个官员可能选中同一个糖果。接下来，被选中的 $1$ 到 $2$ 个糖果会被带离糖果王国，本轮次结束。
对于第一轮次，官员 BBetula 从第 $1$ 个糖果开始，官员 CBetula 从第 $n$ 个糖果开始。

轮次会一直进行，直到所有糖果都被带离糖果王国。作为糖果王国的智囊，请你求出糖果依次离开的顺序吧～

# 输入格式

一行，三个正整数 $n,k,m$ 。保证 $1≤n≤1000$ ， $1≤k,m≤n$ 。

# 输出格式

输出若干行，每行分别为每一轮被带离王国的糖果的编号，若有两个糖果被带离，优先输出官员 BBetula 带离的糖果编号，两个数中间用一个空格分隔。

# 输入样例

10 4 3

# 输出样例

	4 8
	9 5
	3 1
	2 6
	10
	7

# 样例解释

第一个轮次中，官员 BBetula 从第 $1$ 个糖果的位置开始逆时针数 $4$ 个糖果，到达第 $4$ 个糖果的位置；官员 CCBetula 从第 $10$ 个糖果的位置开始顺时针数 $3$ 个糖果，到达第 $7$ 个糖果的位置。在第二轮次中，官员 BBetula 将从第 $5$ 个糖果的位置开始，官员 CCBetula 将从第 $10$ 个糖果的位置开始，依此类推。

# 题解：环状链表

直接用一个环状链表模拟整个过程即可，但是实现时细节较多，具体见代码。

时间复杂度： $O(n^2)$ 。

参考代码：

	#include <stdio.h>

	int n, k, m, size;

	struct Node
	{
	int prev, next, id;
	} node[1010];

	void Init()
	{
	size = n;
	node[1].prev = n, node[1].next = 2, node[1].id = 1;
	node[n].prev = n - 1, node[n].next = 1, node[n].id = n;

	for (int i = 2; i < n; ++ i)
	{
	node[i].prev = i - 1;
	node[i].next = i + 1;
	node[i].id = i;
	}

	return;
	}

	void Delete(int id)
	{
	node[node[id].prev].next = node[id].next;
	node[node[id].next].prev = node[id].prev;
	-- size;

	return;
	}

	int main()
	{
	// freopen("M.in", "r", stdin);
	// freopen("M.out", "w", stdout);

	scanf("%d%d%d", &n, &k, &m);
	Init();
	int bInd = 1, cInd = n;

	while (size)
	{
	for (int i = 1; i < k; ++ i)
	bInd = node[bInd].next;

	printf("%d ", bInd);

	if (size)
	{
	for (int i = 1; i < m; ++ i)
	cInd = node[cInd].prev;

	if (cInd != bInd)
	printf("%d", cInd);
	}

	puts("");
	Delete(bInd);

	if (bInd == cInd) // 会进行两次 Delete，大小只能减 1
	++ size;

	bInd = node[bInd].next;
	Delete(cInd);

	if (bInd == cInd) // 说明 bInd 被拿走了，bInd 再往下移一格
	bInd = node[bInd].next;

	cInd = node[cInd].prev;
	}

	return 0;
	}

链表