At time 0, R red frogs and G green frogs are sitting on a straight line. All the positions of the frogs are non-negative integer numbers. Every second, all the frogs jump. Each of the frogs has its own velocity, i.e., every second the i-th frog jumps Vi units to its left or right depending on the color. Every red frog jumps to its right, and every green frog jumps to its left. The line is divided into N + 1 contiguous segment. The left end of the first segment is always 0 and the right end of the N + 1-st segment is 109. The segments are denoted by a sequence of N positive integers. For example, if N = 1 and the sequence has 1 integer number 10, then there are two segments, one is from 0 to 10 and another is from 10 to 109, both inclusive. You are given the initial positions of all the R+G frogs and a sequence of positive integers describing the segments. Find the minimum time it will take for all the frogs to reach a single segment. A frog is said to be on a segment if and only if it’s sitting on some points inside the segment (including the endpoints). Please note that a frog is not said to be inside a segment when it’s jumping. Please note that, when a frog is on any of the N intermediate boundary points, they can be considered to be part of either the left or the right segment. Input Input starts with a single positive integer, T ≤ 10, on a single line, denoting the number of test cases. The first line of each test cases will be a blank line. Next line will contain three positive integers R, G and N (1 ≤ R, G ≤ 100, 000, 1 ≤ N ≤ 100, 000). Next five lines will be as follows:
2/2 10000 20 10000 1000000 221 12 99 100 1000 1001 100 200 100 Sample Output Case 1: 0 Case 2: 1