Hats Off

Input: Standard Input

Output: Standard Output

It’s the Wild West. But things are not quite well here, now. Last few months, many trains have been robbed by the mysterious and vicious bandit called ‘El Diablo’. The railroad company has offered a reward of about $150000 for the one who can stop him. That’s why John Cooper is trying to catch him.

But the task is not that easy as it looks. That’s why John made a team and planned to chase after the ‘El Diablo’. After a lot of hard work and with mild plans, they finally managed to surround him in a room. But the problem is that the only door of the room is locked and it can’t be unlocked other than finding a combination.

There are n stones scattered outside the room. Each of them is equal in size but labeled by an integer number. The door has n holes numbered from 1 to n. Any hole can contain at most one stone. In the upper side of the door, m pairs of integers are written. Each of them denotes a range of some consecutive holes.

John is trying to arrange the stones in the holes such that, the maximum difference of the maximum labeled stone and the minimum labeled stone in any range is minimized. If John can place them in the best possible way, then the door will be unlocked.

El Diablo will escape if it takes more than 5 hours. Cause he is digging a hole which leads to a cave. If he reaches the cave, all the plans and hark works will be in vain, because he can escape through the cave. That’s why John is seeking your help. Since John is not a programmer, he asks you to write a program which will solve this problem and unlock the door. So, Hats off to you for helping John. May be you will get a share of the reward if you can unlock the door.

Input

First line of the input will contain the number of cases T (<=300). Then T cases follow.

Each case will start with an integer n ( 1 <= n <= 30 ). The next line will contain n integers denoting the labels of the stones. The next line will contain an integer m ( 1 <= m <= 5 ). Each of the next m lines will contain two integers a b ( 1 <= a <= b <= n ) denoting all the holes from a to b (inclusive). Each of the integers will be fit into a 32 bit signed integer.

Output

For each case, print the case number and the desired result as shown below.

Sample Input Output for Sample Input

1 2 4

1 2

2 3

1 2 3 4

1 4

Case 1: 2

Case 2: 3

Problemsetter: Jane Alam Jan

Special Thanks: Manzurur Rahman Khan