1406: #6080. ZQC 的预言

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

众所周知,ZQC 有一堆基友,他们经常在一起打比赛。他们现在在打 LOJ 的一场比赛,这场比赛一共有 n(1≤n≤50) n(1 \leq n \leq 50) n(1n50) 个参赛者,编号为从 1 1 1n n n。每个参赛者都会得到一个分数。

据说 ZQC 的数学非常好,他可以在一定程度上预知比赛的结果。由于选手的成绩是基于实力而上下波动的,假设所有选手的分数都会在 [li,ri](0≤li≤ri≤109) [l_i, r_i](0 \leq l_i \leq r_i \leq 10 ^ 9) [li,ri](0liri109) 之间随机均匀分布,由于 ZQC 非常了解她们,所以 ZQC 可以知道每个选手的大概名次,从而给出大致上预测每个名次可能性最高的选手。

给定选手个数 n n n,以及每个选手的最后得分范围 [li,ri] [l_i, r_i] [li,ri],你能算出最可能获得第 i i i 名的选手编号吗?(得分越高,排名越靠前)

输入格式

第一行为 T(1≤T≤15) T(1 \leq T \leq 15) T(1T15),表示测试数据组数。

对于每组测试数据,第一行一个正整数 n n n,表示参赛选手总数。
接下来 n n n 行,每行包括两个正整数 li l_i liri r_i ri,表示第 i i i 个选手的得分范围。

输出格式

对于第 i i i 组测试数据,输出一行,首先是 Case i:,接下来是包含 n n n 个数字,第 j j j 个数字表示获得第 j j j 名可能性最高的选手编号,以空格分割。

样例

样例输入

2
2
1 6
4 9
8
0 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9

样例输出

Case 1: 1 2
Case 2: 1 2 3 4 5 6 7 8

数据范围与提示

如果存在两个以上选手在 10−610 ^ {-6} 106 的误差范围内具有相同的可能性,输出编号靠前的选手。