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