During the COVID-19 pandemic, Pascal, like many others, has become [an expert at cooking pasta](https://xkcd.com/2287/). He's become so talented that he's decided to open his own restaurant! The challenge is that restaurants today must follow strict capacity guidelines to reduce the virus's spread. He's got the cooking covered, but will need help optimizing the seating logistics in order to achieve a good trade-off between a booming business and responsible social distancing.

On a certain day, Pascal's restaurant is divided into \(N\) open seating sections (numbered from \(1\) to \(N\)), with \(S_i\) customers initially sitting in each section \(i\). To keep business strong, but seating capacity manageable, Pascal insists that each section \(i\) must seat between \(X_i\) and \(X_i + Y_i\) customers, inclusive.

In an attempt to achieve this, he may repeatedly choose a customer to politely (yet forcibly) relocate from their current seating section to a different section of Pascal's choice.

Customers would be annoyed by too much shuffling about, so Pascal has asked for your help in determining the minimum number of such relocations necessary. If the criteria cannot all be met after any number of relocations, you should report a value of \(-1\) instead.

In order to reduce the size of the input, the above values will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(S_{1..K}\), \(X_{1..K}\), and \(Y_{1..K}\), as well as the three quadruples of constants \((A_S, B_S, C_S, D_S)\), \((A_X, B_X, C_X, D_X)\), and \((A_Y, B_Y, C_Y, D_Y)\), and must then compute \(S_{(K+1)..N}\), \(X_{(K+1)..N}\), and \(Y_{(K+1)..N}\) as follows:

\(S_i = (A_S * S_{i-2} + B_S * S_{i-1} + C_S)\text{ modulo }D_S\) for \(i > K\)
\(X_i = (A_X * X_{i-2} + B_X * X_{i-1} + C_X)\text{ modulo }D_X\) for \(i > K\)
\(Y_i = (A_Y * Y_{i-2} + B_Y * Y_{i-1} + C_Y)\text{ modulo }D_Y\) for \(i > K\)

The sum of \(N\) across all \(T\) days is at most 10,000,000.

# Input

Input begins with an integer \(T\), the number of days. For each day, there are 7 lines:

The first line contains the 2 space-separated integers \(N\) and \(K\).

The second line contains the \(K\) space-separated integers \(S_{1..K}\).

The third line contains the 4 space-separated integers \(A_S\), \(B_S\), \(C_S\), and \(D_S\).

The fourth line contains the \(K\) space-separated integers \(X_{1..K}\).

The fifth line contains the 4 space-separated integers \(A_X\), \(B_X\), \(C_X\), and \(D_X\).

The sixth line contains the \(K\) space-separated integers \(Y_{1..K}\).

The seventh line contains the 4 space-separated integers \(A_Y\), \(B_Y\), \(C_Y\), and \(D_Y\).

# Output

For the \(i\)th day, print a line containing *"Case #i: "* followed by a single integer, either the minimum number of customer relocations required, or \(-1\) if it's impossible.

# Constraints

\(1 \le T \le 100\)
\(2 \le N \le 1,000,000\)
\(2 \le K \le N\)
\(0 \le A_S, B_S, C_S, A_X, B_X, C_X, A_Y, B_Y, C_Y \le 1,000,000,000\)
\(1 \le D_S, D_X, D_Y \le 1,000,000,000\)
\(0 \le S_i < D_S\)
\(0 \le X_i < D_X\)
\(0 \le Y_i < D_Y\)

# Explanation of Sample

On the first day, Pascal divides his restaurant into 2 seating sections, with \(S = [10, 20]\), \(X = [9, 21]\), and \(Y = [0, 0]\). In other words, the first section initially has 10 customers but needs to have exactly 9, while the second initially has 20 but needs to have exactly 21. Relocating a single customer from the first section to the second would satisfy both requirements.

On the second day, each section needs to end up with anywhere between 14 and 18 customers, inclusive. Relocating 4 customers from the second section to the first would accomplish this.

On the third day, it's impossible to satisfy all of the requirements. For example, if 2 customers were relocated from the first section to the second, the first section would be left with fewer than its required minimum of 2 customers.

On the fifth day, \(S = [15, 12, 2, 19, 3]\), \(X = [1, 9, 3, 1, 3]\), and \(Y = [0, 6, 9, 9, 8]\).