B"Isaac begins his training. There are n running tracks available, and the i -th track ( 1 <= i <= n ) consists of a_i equal-length sections. Given an integer u ( 1 <= u <= 10^9 ), finishing each section can increase Isaac's ability by a certain value, described as follows: You are also given an integer l . You must choose an integer r such that l <= r <= n and Isaac will finish each section of each track l, l + 1, ... , r (that is, a total of sum_{i=l}^r a_i = a_l + a_{l+1} + ldots + a_r sections). Answer the following question: what is the optimal r you can choose that the increase in Isaac's performance is maximum possible? If there are multiple r that maximize the increase in Isaac's performance, output the smallest r . To increase the difficulty, you need to answer the question for q different values of l and u . The first line of input contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The descriptions of the test cases follow. The first line contains a single integer n ( 1 <= n <= 10^5 ). The second line contains n integers a_1, a_2, ldots, a_n ( 1 <= a_i <= 10^4 ). The third line contains a single integer q ( 1 <= q <= 10^5 ). The next q lines each contain two integers l and u ( 1 <= l <= n, 1 <= u <= 10^9 ) -- the descriptions to each query. The sum of n over all test cases does not exceed 2 cdot 10^5 . The sum of q over all test cases does not exceed 2 cdot 10^5 . For each test case, output q integers: the i -th integer contains the optimal r for the i -th query. If there are multiple solutions, output the smallest one. For the 1 -st query in the first test case: Both choices yield the optimal increase in performance, however we want to choose the smallest r . So we choose r = "...