In a desert city with a hilly landscape, the city hall decided to level the road surface by purchasing a dump truck. The road is divided into $$$n$$$ sections, numbered from $$$1$$$ to $$$n$$$ from left to right. The height of the surface in the $$$i$$$-th section is equal to $$$a_i$$$. If the height of the $$$i$$$-th section is greater than $$$0$$$, then the dump truck must take sand from the $$$i$$$-th section of the road, and if the height of the $$$i$$$-th section is less than $$$0$$$, the dump truck must fill the pit in the $$$i$$$-th section of the road with sand. It is guaranteed that the initial heights are not equal to $$$0$$$.

When the dump truck is in the $$$i$$$-th section of the road, it can either take away $$$x$$$ units of sand, in which case the height of the surface in the $$$i$$$-th section will decrease by $$$x$$$, or it can fill in $$$x$$$ units of sand (provided that it currently has at least $$$x$$$ units of sand in its bed), in which case the height of the surface in the $$$i$$$-th section of the road will increase by $$$x$$$.

The dump truck can start its journey from any section of the road. Moving to an adjacent section on the left or right takes $$$1$$$ minute, and the time for loading and unloading sand can be neglected. The dump truck has an infinite capacity and is initially empty.

You need to find the minimum time required for the dump truck to level the sand so that the height in each section becomes equal to $$$0$$$. Note that after all movements, the dump truck may still have sand left in its bed. You need to solve this problem independently for the segments numbered from $$$l_i$$$ to $$$r_i$$$. Sand outside the segment cannot be used.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the number of sections and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$, $$$a_i \neq 0$$$) — the initial height in each section.

The $$$i$$$-th of the following $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the boundaries of the segment of sections for which the minimum time needs to be determined.

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$q$$$ over all test cases do not exceed $$$3 \cdot 10^5$$$.

Output

For each query, output the minimum time required to level the sand in the segment $$$[l_i, r_i]$$$, or $$$-1$$$ if it is impossible.

Note

In the first test case, $$$179$$$ units of sand need to be added to the only section. However, there is nowhere to take it from, so this is impossible.

In the second test case:

In the first query, the dump truck can start its journey at the second section. It can take $$$2$$$ units of sand, after which the height in the second section will become $$$0$$$. Then the dump truck can move to the third section. It can pour $$$1$$$ unit of sand there, after which the height in the third section will become $$$0$$$. Then the dump truck can move to the fourth section. There it can take $$$3$$$ units of sand, after which the height in the fourth section will become $$$0$$$. In total, the dump truck will spend $$$2$$$ minutes on movements.
In the second query, the dump truck can start its journey at the fourth section. It can take $$$3$$$ units of sand, after which the height in the fourth section will become $$$0$$$. Then the dump truck can move to the fifth section. It can pour $$$1$$$ unit of sand there, after which the height in the fifth section will become $$$0$$$. Then the dump truck can move back to the fourth section and then to the third. It can pour $$$1$$$ unit of sand there, after which the height in the third section will become $$$0$$$. Then the dump truck can move to the second section. It can take $$$2$$$ units of sand. Then it can move to the first section. It can pour $$$2$$$ units of sand there, after which the height in the first section will become $$$0$$$. In total, the dump truck will spend $$$5$$$ minutes on movements.
In the third query, the dump truck will not be able to make the height in each section equal to $$$0$$$.

Hills and Pits

Examples