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(1≤n≤50) 个参赛者，编号为从 1 1 1 到 n n n。每个参赛者都会得到一个分数。

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

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

输入格式

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

对于每组测试数据，第一行一个正整数 n n n，表示参赛选手总数。
接下来 n n n 行，每行包括两个正整数 li l_i l​i​​、ri r_i r​i​​，表示第 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} 10​−6​​ 的误差范围内具有相同的可能性，输出编号靠前的选手。

SubmitSubmit RecordStatisticsShowOff!