407022: GYM102688 D Drop the Beat

Kenya North is running for president! The country needs change, and Kenya insists that music will make this happen. However, the elections are coming up, and he needs to solidify his campaign and gain support.

To increase his chances of winning, Kenya composed two presidential songs. The songs $$$A$$$ and $$$B$$$ are $$$n$$$ and $$$m$$$ seconds long, respectively. Each second of these songs has a single note, denoted by $$$A_1, ..., A_n$$$ and $$$B_1, ..., B_m$$$. We label notes with positive integers.

Kenya plans on parading the streets while playing both songs at the same time on infinite loop. They are initially played from the start at the same time. In other words, we extend the sequences $$$A$$$ and $$$B$$$ into the following infinite (periodic) sequences:

• $$$A_1, \ldots, A_n, A_1, \ldots, A_n, A_1, \ldots$$$
• $$$B_1, \ldots, B_m, B_1, \ldots, B_m, B_1, \ldots$$$

In other words, for all positive integers $$$i$$$, $$$A_i = A_{i+n}$$$ and $$$B_i = B_{i+m}$$$.

Of course, $$$n$$$ and $$$m$$$ could be different, so the songs don't necessarily align after the first playing. For example, if song $$$A$$$ has length 4 and contains the notes $$$101, 192, 103, 259$$$ and song $$$B$$$ has length $$$6$$$ and contains the notes $$$134, 77, 66, 141, 52, 78$$$, then the song notes align in the following way: $$$$$$\begin{array}{rrrrrrrrrrrrrr} \text{Song $1$:}& 101 & 192 & 103 & 259 & 101 & 192 & 103 & 259 & 101 & 192 & 103 & 259 & \ldots \\ \text{Song $2$:}& 134 & 77 & 66 & 141 & 52 & 78 & 134 & 77 & 66 & 141 & 52 & 78 & \ldots \\ \end{array}$$$$$$

Your campaign manager and DJ, Musky Melon, notices that there are certain times when more people are listening. It's at times like those that you need to drop the beat! Define the level of the beat drop of a certain segment of time to be the sum of the absolute differences between the corresponding notes of $$$A$$$ and $$$B$$$ during the duration of the beat drop. More formally, if the beat drop lasts from time $$$s$$$ to time $$$t$$$, then the level of the beat drop is: $$$$$$|A_s - B_s| + \ldots + |A_t - B_t|.$$$$$$

For this measure, the lower the better! You want the beat drop level to be as low as you can. To do this, Kenya can use his specialty—autotuning—to adjust the notes of each song. For each beat drop, he chooses an integer $$$x$$$ and then he either increases or decreases all notes of $$$A$$$ by $$$x$$$. Similarly, he also chooses an integer $$$y$$$ and then he either increases or decreases all notes of $$$B$$$ by $$$y$$$. He does this so that the level of the beat drop is minimized. Note that $$$x$$$ and $$$y$$$ must be chosen so that all of the notes of $$$A$$$ and $$$B$$$ after autotuning are still positive integers.

You are given the notes of the songs $$$A$$$ and $$$B$$$. For each time duration Musky Melon drops the beat, determine the lowest beat drop level.

The first line contains a single integer $$$t$$$ denoting the number of test cases.

The first line of each test case contains a single integer $$$n$$$ followed by a line with $$$n$$$ space-seperated integers $$$A_1, A_2, ..., A_n$$$. Similarly, the third line contains a single integer $$$m$$$ followed by a line with $$$m$$$ space-seperated integers $$$B_1, B_2, ..., B_m$$$.

The next line contains $$$q$$$, the number of time segments Musky Melon wants to drop the beat. $$$q$$$ lines follow, the $$$i$$$th line describing a query containing two space-seperated integers, $$$s_i$$$ and $$$t_i$$$, denoting the start and end time of the beat drop, inclusive.

For each time duration, output a single line containing the minimum beat drop level for that time duration.

Here, let

• $$$N$$$ be the sum of the $$$n$$$s across all test cases in a single file, and

• $$$M$$$ be the sum of the $$$m$$$s across all test cases in a single file.

For all subtasks

$$$1 \le t \le 30$$$

$$$1 \le n, m, N, M \le 60000$$$

$$$1 \le q \le 3$$$

$$$1 \le s_i \le t_i \le 10^{12}$$$

$$$1 \le A_k, B_k \le 10^6$$$

Subtask 1 (11 points):

$$$1 \le n, m, N, M \le 400$$$

$$$1 \le s_i \le t_i \le 10^3$$$

Subtask 2 (10 points):

$$$1 \le s_i \le t_i \le 75000$$$

Subtask 3 (26 points):

$$$1 \le n, m, N, M \le 400$$$

Subtask 4 (31 points):

$$$1 \le n, m, N, M \le 30000$$$

$$$n$$$ and $$$m$$$ do not have any common factors other than $$$1$$$

Subtask 5 (9 points):

$$$n$$$ and $$$m$$$ do not have any common factors other than $$$1$$$

Subtask 6 (8 points):

$$$1 \le n, m, N, M \le 30000$$$

Subtask 7 (5 points):

No further restrictions.

2
4
101 192 103 259
6
134 77 66 141 52 78
3
1 3
2 7
129 129
10
201 119 47 175 90 12 253 82 179 8
9
236 128 175 152 68 167 55 182 199
3
176 195
73 258
26 227

148
292
0
1635
15081
16486

3
4
101 192 103 259
6
134 77 66 141 52 78
2
53 1271
3 12
10
201 119 47 175 90 12 253 82 179 8
9
236 128 175 152 68 167 55 182 199
3
103 202
45 95
49 77
10
201 119 47 175 90 12 253 82 179 8
9
236 128 175 152 68 167 55 182 199
2
72 181
52 158

66247
505
7822
4077
2395
8825
8692

The first sample case is valid for subtasks $$$1$$$, $$$2$$$, $$$3$$$, $$$6$$$ and $$$7$$$.

The second sample case is valid for subtasks $$$2$$$, $$$3$$$, $$$6$$$ and $$$7$$$.