K. Know Your Duration of Stay
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You work at Interplanetary Clerks for Population Convenience, a company that handles various operations. In particular, your job is to assist people in filling out their visa applications for foreign embassies.

Today, you were shocked by the news: unexpectedly, the newly elected parliament of the planet Yllesynbelliawniffwrdd decided to abolish the usual calendar starting in the current year 2024 and create their own, with $$$n$$$ months and $$$a_1, a_2, \ldots, a_n$$$ days in them! It would be just a funny joke... if you didn't have to work with clients who now have to fill out their visa applications according to the new calendar.

The main difficulty, however, is calculating the desired duration of a visa. Clearly, if you arrive and depart the same month on the 5th and 17th days, respectively, then you need a 13-day visa, as both the arrival and departure days count. But what about longer trips? Fortunately for you, Yllesynbelliawniffwrdd does not issue visas that last more than a full year, so you don't have to worry about overly long time periods. However, since all the clients are asking for your help right now, you need to act really fast!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100\,000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 100\,000$$$), denoting the number of months in the new calendar and the number of clients.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \ge 1$$$, $$$\sum_{i=1}^{n} a_i \le 10^9$$$): the durations of the months.

Each of the next $$$m$$$ lines contains four integers $$$s_d$$$, $$$s_m$$$, $$$e_d$$$, $$$e_m$$$ ($$$1 \le s_m, e_m \le n$$$, $$$1 \le s_d \le a_{s_m}$$$, $$$1 \le e_d \le a_{e_m}$$$), meaning that the client wants to arrive on day $$$s_d$$$ of month $$$s_m$$$ and depart on day $$$e_d$$$ of month $$$e_m$$$. The departure day is less than a year away from the arrival day, so the year is not specified.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$100\,000$$$.

Output

For each test case and each client, print a single integer $$$d$$$ ($$$1 \le d \le \sum_{i=1}^{n} a_i$$$), denoting the required minimum visa duration in days. Note that the answer never exceeds one year.

Example
Input
2
12 3
31 29 31 30 31 30 31 31 30 31 30 31
16 11 15 12
16 11 16 11
2 12 4 4
9 1
998 244 353 998 244 353 998 244 353
2 1 1 1
Output
30
1
125
4785
Note

In the first test case, the first client arrives on the day of the ICPC Belarus Regional Contest and departs on the day of the ICPC Northern Eurasia Finals. Their visa duration should be at least $$$30$$$ days.

In the last test case, the only client's visa should be issued for the entire year.