问题 A: Chords

Imagine a mystical forest where a magic piano with n keys resides. Each key of this piano represents a note, denoted by positive integers from 1 through n. In musical terms, a chord is defined as a set of notes played together in harmony. The type or class of a chord is categorized based on the difference between its root note (the lowest note) and the other notes in the chord. For instance, the chord class known as minor triad includes all chords of the format {x, x + 3, x + 7}. Similarly, the chord class dominant seventh includes all chords that follow the pattern {x, x + 4, x + 7, x + 10}. For each key x on the piano (which produces the note x), you can play it with ax different strengths, each of which produces a unique sound. As a result, you can produce ax distinct sounds from that note. More interestingly, for a minor triad with root note x as an example, you can produce ax × ax+3 × ax+7 unique sounds. Now, consider a given chord class represented by {x + b1, x + b2, ..., x + bm}. Your task is to calculate the total number of different sounds you can produce when you are free to choose any root note x

The first line of the input contains a single integer T (1 ≤ T ≤ 103 ), denoting the number of test cases. The first line of each test case contains two integers n, m (1 ≤ m ≤ n ≤ 5 × 105 ) separated by space, denoting the number of keys in the piano and the number of notes in the given chord class. The second line of each test case contains n positive integers a1, . . . , an (0 < ax < 1062125569), each representing the number of different strengths that can be applied to the corresponding key x. The third line of each test case contains m ascending integers b1, . . . , bm (0 = b1 < b2 < . . . < bm < n), denoting the given chord class. It is guaranteed that the sum of n over all test cases will not exceed 106 .

For each test case, output the answer modulo 1062125569 in a single line. 

1
5 2
3 4 2 5 1
0 2

28