Problem1181--加油站

1181: 加油站

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 402  Solved: 178
[Submit] [Status] [Web Board] [Creator:]

Description

环形公路上有n个加油站,编号 1~n ,第i个加油站可以加油 pi加仑,从 i到 i+1需要 qi加仑汽油。你可以选任意一个加油站作为起点,初始油箱为空。你的任务是选择一个加油站作为起点,使得可以走完一圈后回到起点。

Input

第一行包含一个整数T,代表测试用例的数目。
每组测试用例第一行包含一个正整数n,代表加油站个数(n<=100000)。
第二行包含 n个正整数 pi;
第三行包含 n 个正整数qi;

Output

对于每组样例,若有解,输出编号最小的起点"Case %d: Possible from station %d"。若无解,输出"Case %d: Not possible"

Sample Input

2
5
1 1 1 1 1
1 1 2 1 1
7
1 1 1 10 1 1 1
2 2 2 2 2 2 2

Sample Output

Case 1: Not possible
Case 2: Possible from station 4

Source/Category