提示: 欢迎访问OurACM平台。
Problem 2160 Mountain climbing

Accept: 42    Submit: 207
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

又这是一个关于登山的问题。现有n座山位于一条直线上,每座山可以看成一条垂直于地面的线段,一端点在地面上,这些山编号从左往右为1到n,第i座山位于xi高为hi。

对于任意的两座山a和b,如果a的顶端能看见b的顶端,则他们可以用绳索连接。a能看见b,当且仅当他们顶端的连线不能穿过其他山或者触摸到其他山。若a与b能用绳索连接那么登山者可以用一个单位的时间从a到b或者从b到a(不论绳索多长,且只能从左边往右边)。

现在我们的目的地第n座山,现在要你求出每座山到达第n座山要需要的最短时间。

Input

输入第一行为一个正整数T(1<= T < =20),表示有T组数据。

每组数据:

第一行一个整数n(1<=n<=100 000)表示一共n座山。

接下去n行每行两个数xi, hi。 (0<xi,hi<=10^8)

数据保证输入的xi(X1<...<Xi-1<Xi<Xi+1<...<Xn).

Output

对于每个询问,先输出“Case#i: ”,i表示第i组数据,接着输出n个整数,第i个数表示从第i座山出发最少要花费多少时间能到达目的地。

Sample Input

1 5 1 5 2 1 3 2 4 3 5 4

Sample Output

Case#1: 1 3 2 1 0

Submit  Back  Status  Discuss