1706. [POJ 3145] 永远和谐

【题目描述】

我们相信宇宙中的每个物种最终都能和谐共处；相信信任，耐心，仁慈，忠诚将在地球上的所有生命间长存；相信人类未曾停止的冲突与争斗将被尊重与合作取代。和谐——许多人梦想的社会状态，但现在看上去它是那么的遥不可及……

幸运的是，解锁通往真正和谐社会钥匙的方法已经被一组哲学家发现。它被记录在一颗最近坠落的奇怪陨石上。你需要破译那些看上去随机的符号后隐藏的真正意义……更精确地，你需要写一个程序，对一个初始为空的集合S支持以下两种操作：

1. B X：将数X加入集合S。第K个形如B X的操作在时间K发生，保证在这个操作之前X不在S中。

2. A Y：对于当前S中所有的数，找到模Y余数最小的。如果有多个，应当选择输入中最后出现的那个。返回这个元素被加入S的时刻。

据说如果能在尽量短的时间内计算出答案，人类就能达到真正的大和谐。你的任务是写一个程序帮助我们。

【输入格式】

输入包含多组数据。

每组数据的第一行有一个整数T，1<=T<=40000。

接下来T行每行有一个操作，是“B X”或者“A Y”之一，其中1<=X<=500000,1<=Y<=1000000.

输入结束标志为T=0，不必处理。

【输出格式】

对每组数据按照样例的格式输出。对每个“A Y”操作，在单独的一行中输出查询结果。如果S中没有元素则输出-1。两组数据间用一个空行隔开。

【样例输入】

5

B 1

A 5

B 10

A 5

A 40

2

B 1

A 2

0

【样例输出】

Case 1:

1

2

1

Case 2:

1

【来源】

POJ 3145 Harmony Forever