You had long wanted a spaceship, and finally you bought a used one yesterday! You have heard that the most difficult thing on spaceship driving is to stop your ship at the right position in the dock. Of course you are no exception. After a dozen of failures, you gave up doing all the docking process manually. You began to write a simple program that helps you to stop a spaceship.
First, you somehow put the spaceship on the straight course to the dock manually. Let the distance to the limit line be x[m], and the speed against the dock be v[m/s]. Now you turn on the decelerating rocket. Then, your program will control the rocket to stop the spaceship at the best position.
Your spaceship is equipped with a decelerating rocket with n modes. When the spaceship is in mode-i (0 ≤ i < n), the deceleration rate is ai[m/s2]. You cannot re-accelerate the spaceship. The accelerating rocket is too powerful to be used during docking. Also, you cannot turn off-and-on the decelerating rocket, because your spaceship is a used and old one, once you stopped the rocket, it is less certain whether you can turn it on again. In other words, the time you turn off the rocket is the time you stop your spaceship at the right position.
After turning on the deceleration rocket, your program can change the mode or stop the rocket at every sec- ond, starting at the very moment the deceleration began. Given x and v, your program have to make a plan of deceleration. The purpose and the priority of your program is as follows:
The first line of the input consists of a single integer c, the number of test cases.
Each test case begins with a single integer n (1 ≤ n ≤ 10), the number of deceleration modes. The following line contains n positive integers a0, . . . , an-1 (1 ≤ ai ≤ 100), each denoting the deceleration rate of each mode.
The next line contains a single integer q (1 ≤ q ≤ 20), and then q lines follow. Each of them contains two positive integers x and v (1 ≤ x, v ≤ 100) defined in the problem statement.
For each pair of x and v, print the result in one line. A blank line should be inserted between the test cases.
1 3 2 4 6 4 10 100 2 3 10 6 7 6
crash try again good 1.000 perfect