ZQC 的预言

传统 1000 ms 256 MiB

数学多项式 / 形式幂级数 概率与期望

$6$ 通过 $20$ 提交

题目描述

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

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

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

输入格式

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

对于每组测试数据：

• 第一行一个正整数 $n$，表示参赛选手总数。
• 接下来 $n$ 行，每行包括两个正整数 $l_i$、$r_i$，表示第 $i$ 个选手的得分范围。

输出格式

对于第 $i$ 组测试数据，输出一行，首先是 Case i:，接下来是包含 $n$ 个数字，第 $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^{-6}$ 的误差范围内具有相同的可能性，输出编号靠前的选手。