Description

Casual game player $Q$ has not only achieved excellent results in algorithm contests, but also ranks very high in a diamond-collecting game.

This game has $n$ different types of diamonds, numbered from $1$ to $n$. Player $Q$ has played this game for a long time. For type $i$, he has already collected $a_i$ diamonds. The biggest feature of this game is that there is only one way to obtain diamonds: buying them from the shop. Specifically, the unit price of type $i$ is $b_i$ coupons. To encourage players to spend money, there is no quantity limit for any type of diamond: as long as you are willing to pay, you can have as many diamonds as you want. However, the game does not have a “discard item” feature, so $Q$ cannot discard diamonds to complete the task.

Recently, the game launched a limited-time achievement task. Players who complete it can get an honorary title. The completion condition is:

Given positive integers $k$ and $m$, for any integer $x \ (x\ge 2^k)$, the value
$a_{x}+a_{\lfloor\frac{x}{2}\rfloor}+a_{\lfloor\frac{x}{4}\rfloor}+a_{\lfloor\frac{x}{8}\rfloor}+...+a_{\lfloor\frac{x}{2^k}\rfloor}$
must be a multiple of $m$.

Of course, skilled player $Q$ wants to complete this limited-time achievement task, but before spending money he wants to know how many coupons he needs to complete it. Please write a program to help $Q$ compute the minimum number of coupons required.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains $9$ positive integers $n, k, m, p, SA, SB, SC, A, B$, where $n$ is the number of diamond types, and $k, m$ are the task conditions.

To reduce the input size to some extent, arrays $a[]$ and $b[]$ are generated by the following code:

unsigned int SA, SB, SC;int p, A, B;
unsigned int rng61(){
	SA ^= SA << 16;
	SA ^= SA >> 5;
	SA ^= SA << 1;
	unsigned int t = SA;
	SA = SB;
	SB = SC;
	SC ^= t ^ SA;
	return SC;
}
void gen(){
	scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);
	for(int i = 1; i <= p; i++)scanf("%d%d", &a[i], &b[i]);
	for(int i = p + 1; i <= n; i++){
		a[i] = rng61() % A + 1;
		b[i] = rng61() % B + 1;
	}
}

Output Format

For each test case, output one integer per line, the minimum number of coupons required.

2
3 1 2 3 11111 22222 33333 1 1
1 5
2 3
3 6
7 2 3 7 11111 22222 33333 1 1
6 9
4 5
3 7
5 2
2 4
1 7
9 6

3
14

Hint

• $1 ≤ T ≤ 10$.
• $1 ≤ k ≤ 10$ and $2^k ≤ n$.
• $1 ≤ p ≤ min(n, 100000)$, $10000 ≤ SA, SB, SC ≤ 1000000$.
• $1 ≤ A, B, ai, bi ≤ 10^7$.

Constraints:

Subtask 1 ($30$ points): $1 ≤ n ≤ 1000$ and $m = 2$.

Subtask 2 ($40$ points): $1 ≤ n ≤ 10^5$ and $m ≤ 200$.

Subtask 3 ($30$ points): $1 ≤ n ≤ 10^7$ and $m ≤ 200$.

Translated by ChatGPT 5