Facebook Prime is a top-secret subscription service being developed to disrupt the online shopping space. (Or maybe there's no such service — we're not telling.) A central focus of the service is preventing package theft, something which has become all too common in today's delivery-driven world. As a member of its engineering team, you wish to model some worst-case scenarios to stress test the vulnerability of poorly-run mailrooms.

In the *very* worst cases, mailroom managers will actually leave mailbox keys inside mailboxes themselves. This means that if one mailbox were to be broken into, a series of other mailboxes could be compromised as well. Suppose a particular mailroom has \(N\) mailboxes (numbered from \(1\) to \(N\)), each with a corresponding key, and \(M\) packages (numbered from \(1\) to \(M\)). The \(i\)th mailbox has a capacity of \(S_i\), meaning that it can store a set of objects (packages or keys) as long as the sum of their sizes doesn't exceed \(S_i\). The size of the \(i\)th package is \(P_i\), and the size of each key is \(X\).

For the purposes of our model, a valid mailroom arrangement must satisfy all of the following conditions:

1. Each package is either inside a mailbox, or is entirely absent.
2. Each key is either inside a mailbox (possibly its own corresponding mailbox), or is entirely absent.
3. Each mailbox contains at most 1 package.
4. No mailbox's capacity is exceeded.

Suppose a thief enters a validly arranged mailroom and forcibly breaks into just one mailbox (without needing a key). If the mailbox contains a package, then they'll obtain it; if the mailbox contains any keys, the thief can then proceed to open each of those keys' corresponding mailboxes and repeat the process (gaining access to any packages and keys they contain, and so on).

Given the specifications of a mailroom, you wish to determine, among all possible valid arrangements, the largest number of packages that may be obtained after a thief forcibly breaks into a single mailbox.

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}\) and \(P_{1..K}\), as well as the two quadruples of constants \((A_S, B_S, C_S, D_S)\) and \((A_P, B_P, C_P, D_P)\), and must then compute \(S_{(K+1)..N}\) and \(P_{(K+1)..M}\) as follows:

\(S_i = ((A_S * S_{i-2} + B_S * S_{i-1} + C_S)\text{ modulo }D_S) + 1\) for \(i > K\)
\(P_i = ((A_P * P_{i-2} + B_P * P_{i-1} + C_P)\text{ modulo }D_P) + 1\) for \(i > K\)

# Constraints

\(1 \le T \le 90\)
\(2 \le N \le 1,000,000\)
\(2 \le M \le 1,000,000\)
\(2 \le K \le min(N, M)\)
\(1 \le X \le 1,000,000,000\)
\(0 \le A_S, B_S, C_S, A_P, B_P, C_P \le 1,000,000,000\)
\(1 \le D_S, D_P \le 1,000,000,000\)
\(1 \le S_i \le D_S\)
\(1 \le P_i \le D_P\)

The sum of \(N + M\) across all mailrooms is at most 10,000,000.

# Input

Input begins with an integer \(T\), the number of mailrooms to be modeled. For each mailroom, there are 5 lines:

The first line contains the 4 space-separated integers \(N\), \(M\), \(K\), and \(X\).

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 \(P_{1..K}\).

The fifth line contains the 4 space-separated integers \(A_P\), \(B_P\), \(C_P\), and \(D_P\).

# Output

For each mailroom, print a line containing *"Case #i: "*, followed by a single integer, the maximum possible number of packages which could be stolen by forcibly breaking into a single mailbox in any valid mailroom arrangement.

# Explanation of Sample

For the first mailroom, \(S = [10, 10, 10]\) and \(P = [9, 9, 9]\). If each mailbox contains a package, the 1st mailbox contains the 2nd mailbox's key, and the 2nd mailbox contains the 3rd mailbox's key, then a thief breaking into the 1st mailbox would gain access to the 2nd mailbox followed by the 3rd, obtaining all three packages in the process.

For the second mailroom, \(S = [10, 10, 10]\) and \(P = [10, 10, 10]\). If the 1st and 3rd mailboxes each contain a package, while the 2nd mailbox contains all three mailboxes' keys, then a thief breaking into the 2nd mailbox would gain access to the other two mailboxes and their packages.

For the third mailroom, \(S = [10, 10, 10]\) and \(P = [11, 11, 11]\). No package can fit within any mailbox.

For the fourth mailroom, \(S = [2, 11, 9, 7]\) and \(P = [10, 9, 10, 11]\). It's possible to arrange the mailroom such that two packages are obtainable by a thief, but three or more can never be obtained.

For the fifth mailroom, \(S = [15, 3, 5, 11, 7, 17, 5]\) and \(P = [7, 8, 11, 10, 3]\).