Thank you for participating in Kick Start 2019 Round G.

**Cast**

Book Reading: Written and prepared by Jonathan Irvin Gunawan.

The Equation: Written by Zhang Chen and prepared by Jonathan Irvin Gunawan.

Shifts: Written by Himanshu Jaju and prepared by Raihat Zaman Neloy.

Solutions, other problem preparation, reviews and contest monitoring by Bartosz Kostka, Himanshu Jaju, Hsin-Yi Wang, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu, Raihat Zaman Neloy, Yang Xiao, and Zhang Chen.

Analysis authors:

- Book Reading: Jonathan Irvin Gunawan
- The Equation: Reyno Tilikaynen
- Shifts: Sadia Atique

Supervin is a librarian handling an ancient book with **N** pages, numbered from 1 to **N**.
Since the book is too old, unfortunately **M** pages are torn out: page number
**P _{1}**,

Today, there are **Q** lazy readers who are interested in reading the ancient book.
Since they are lazy, each reader will not necessarily read all the pages.
Instead, the i-th reader will only read the pages that are numbered multiples of
**R _{i}** and not torn out.
Supervin would like to know the sum of the number of pages read by each reader.

The first line of the input gives the number of test cases, **T**.
**T** test cases follow.
Each test case begins with a line containing the three integers **N**, **M**, and **Q**,
the number of pages in the book, the number of torn out pages in the book, and the number of
readers, respectively.
The second line contains **M** integers, the i-th of which is **P _{i}**.
The third line contains

For each test case, output one line containing `Case #x: y`

, where `x`

is
the test case number (starting from 1) and `y`

is the total number of pages that will
be read by all readers.

Time limit: 40 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **P _{1}** <

1 ≤

1 ≤ **M** ≤ **N** ≤ 1000.

1 ≤ **Q** ≤ 1000.

1 ≤ **M** ≤ **N** ≤ 10^{5}.

1 ≤ **Q** ≤ 10^{5}.

Sample Input

3 11 1 2 8 2 3 11 11 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1000 6 1 4 8 15 16 23 42 1

Sample Output

Case #1: 7 Case #2: 0 Case #3: 994

In sample case #1, the first reader will read the pages numbered 2, 4, 6, and 10. Note that the page numbered 8 will not be read since it is torn out. The second reader will read the pages numbered 3, 6, and 9. Therefore, the total number of pages that will be read by all readers is 4 + 3 = 7.

In sample case #2, all pages are torn out so all readers will read 0 pages.

In sample case #3, the first reader will read all the pages other than the six given pages.

The laws of the universe can be represented by an array of **N** non-negative integers. The i-th of these integers is **A _{i}**.

The universe is *good* if there is a non-negative integer k such that the following equation is satisfied:
(**A _{1}** xor k) +
(

What is the largest value of k for which the universe is good?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case begins with a line containing the two integers **N** and **M**, the number of
integers in **A** and the limit on the equation, respectively.

The second line contains **N** integers, the i-th of which is **A _{i}**, the i-th
integer in the array.

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is
the largest value of k for which the universe is good, or `-1`

if there is no such k.

Time limit: 15 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **N** ≤ 1000.

0 ≤ **M** ≤ 100.

0 ≤ **A _{i}** ≤ 100, for all i.

0 ≤

Sample Input

4 3 27 8 2 4 4 45 30 0 4 11 1 0 100 6 2 5 5 1 5 1 0

Sample Output

Case #1: 12 Case #2: 14 Case #3: 100 Case #4: -1

In sample case #1, the array contains **N** = 3 integers and **M** = 27.
The largest possible value of k that gives a good universe is 12
((8 xor 12) + (2 xor 12) + (4 xor 12) = 26).

In sample case #2, the array contains **N** = 4 integers and **M** = 45.
The largest possible value of k that gives a good universe is 14
((30 xor 14) + (0 xor 14) + (4 xor 14) + (11 xor 14) = 45).

In sample case #3, the array contains **N** = 1 integer and **M** = 0.
The largest possible value of k that gives a good universe is 100
(100 xor 100 = 0).

In sample case #4, there is no value of k that gives a good universe, so the answer is -1.

Aninda and Boon-Nam are security guards at a small art museum.
Their job consists of **N** shifts.
During each shift, at least one of the two guards must work.

The two guards have different preferences for each shift.
For the i-th shift,
Aninda will gain **A _{i}** happiness points if he works,
while Boon-Nam will gain

The two guards will be happy if both of them receive at least **H** happiness points.
How many different assignments of shifts are there where the guards will be happy?

Two assignments are considered different if there is a shift where Aninda works in one assignment but not in the other, or there is a shift where Boon-Nam works in one assignment but not in the other.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case begins with a line containing the two integers **N** and **H**, the number of shifts and the minimum happiness points required, respectively.
The second line contains **N** integers. The i-th of these integers is **A _{i}**, the amount of happiness points Aninda gets if he works during the i-th shift.
The third line contains

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is
the number of different assignments of shifts where the guards will be happy.

Time limit: 40 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

0 ≤ **H** ≤ 10^{9}.

0 ≤ **A _{i}** ≤ 10

0 ≤

1 ≤ **N** ≤ 12.

1 ≤ **N** ≤ 20.

Sample Input

2 2 3 1 2 3 3 2 5 2 2 10 30

Sample Output

Case #1: 3 Case #2: 0

In Sample Case #1, there are **N** = 2 shifts and **H** = 3. There are three possible ways
for both Aninda and Boon-Nam to be happy:

- Only Aninda works on the first shift, while both Aninda and Boon-Nam work on the second shift.
- Aninda and Boon-Nam work on the first shift, while only Aninda works on the second shift.
- Both security guards work on both shifts.

In Sample Case #2, there are **N** = 2 shifts and **H** = 5. It is impossible for both Aninda and
Boon-Nam to be happy, so the answer is 0.

We can solve this test set by naively computing the number of pages that each lazy readers will
read. We can do this by initially having an array `torn`

of **N** booleans, where
`torn[x]`

is true if and only if page x is torn out, and then for each lazy reader i,
we can iterate from 1 to **N**, incrementing our answer only if the value that we iterate is a
multiple of **R _{i}** and not torn out.

The running time of this solution is O(**N** × **Q**).

Let f(x) be the number of pages that are multiples of x and not torn out. To compute f(x), we can
only check whether the pages x, 2x, 3x, ..., floor(**N**/x)x are torn out. Therefore, we can do
this in **N**/x time.

This means that we can compute f(1), f(2), ..., f(**N**) in a total of
**N**(1/1 + 1/2 + ... + 1/**N**) time. 1/1 + 1/2 + ... + 1/**N** is approximately
O(log **N**) (since the n-th harmonic
number is approximately O(log **N**)), so in total f(1), f(2), ..., f(**N**) can be
computed in a total of O(**N** log **N**) time.

After precomputing f(x), we can easily count the number of pages that each lazy readers will read
in O(1). The running time of this solution is O(**N** log **N** + **Q**).

Test Data

We recommend that you practice debugging solutions without looking at the test data.

For the first test set, notice that the maximum value of **k** is 127. This is because each
**A _{i}** is at most 100, so the leading digit of

Hence, we can compute the answer by checking each value of **k** less than 128 and finding the
largest one which produces a sum less than **M**.

For the second test set, the reasoning above tells us that **k** < 2^{50}, which is
too big for us to check every value.

Instead, notice that each bit of **k** only affects a single bit of each **A _{i}**.
We can use this property to compute each bit of

For each 1 ≤ *i* ≤ 50, define *ones(i)* to be the number of rules
**A _{i}** with the

Σ_{1 ≤ j ≤ N} **A _{j}** xor

as:

Σ_{i : i-th bit of k is 1}
2^{i}×*zeroes(i)* +
Σ_{i : i-th bit of k is 0}
2^{i}×*ones(i)*

Note that we can minimize this sum by choosing the *i*-th bit of **k** to be 1 if
*ones(i)* ≥ *zeroes(i)*, or 0 otherwise. Define *f(j)* to be the minimum value
of the above sum over all bits *i* ≤ *j*. We can use *f(j)* to determine if a
feasible value of **k** exists for the lowest *j* bits, which lets us solve this problem
greedily.
The greedy solution is as follows: starting from the most significant bit *i*, check if we
can set it to be one (by adding cost of setting this bit to one and *f(i-1)*). If this value
is less than or equal to **m**, there exists a feasible **k** with the *i*-th bit set
to one. Since we want to set to maximize **k**, it is optimal for us to set this bit to 1.
Otherwise, if the sum is larger than **m**, set the bit to zero. Then iterate by decreasing
**m** by the cost at the current bit and checking the next most significant bit (*i*-1).
In this way, we are able to find the largest feasible **k**.
If *f(i)* is precomputed, the runtime of this algorithm is
O(**N**log(max(**A _{i}**))).

Note that since **A _{i}** ≤ 10

Test Data

We recommend that you practice debugging solutions without looking at the test data.

For each shift, we have three choices,

- Aninda alone guards the shift
- Boon-Nam alone guards the shift
- Both of them guard the shift

We can go through all possible choices for all shifts, and check for how many combinations both of their happiness score is at least **H**.
There are total 3^{N} such combinations possible, enumerating through all of them fits the time limit for test set 1.

For test set 2, we can divide the shifts into 2 sets, each having the size of at most ceil(**N**/2).
We can divide them into two sets, because the choices for each shift are independent of each other.
For each set, we can enumerate every possible combination, and compute happiness score for both of the guards for each combination, which gives us a list of happiness score pairs
for those two sets. Then for each happiness score pair (h_{1}, h_{2}) of the combinations of set 1, we need to count the number of happiness score pairs (p_{1}, p_{2}) of the combinations of set 2, such that
p_{1}+h_{1} ≥ **H** and p_{2}+h_{2} ≥ **H**, which can be converted to p_{1} ≥ **H**-h_{1} and p_{2} ≥ **H**-h_{2}.

Essentially, we can follow these steps below to find the answer.

- Store the happiness score pairs of combinations of both set 1 and set 2 in two arrays, let's call them A
_{1}and A_{2}. - Sort both A
_{1}and A_{2}, by the first value in the pair in decreasing order, then by the second value of the pair in decreasing order. - Iterate through A
_{1}. For each pair (h_{1}, h_{2}) in A_{1}, do the following: - Find the pairs (p
_{1}, p_{2}) in A_{2}where p_{1}is not less**H**- h_{1}. - For each of the pair (p
_{1}, p_{2}) found, add p_{2}to a data structure. - Find the number of elements not less than
**H**- h_{2}in the data structure, add that to answer.

For this approach, we need a data structure that supports these two operations:

- Insert a number in the data structure
- Count number of elements in the data structure not less than a given integer

These two operations can be done in O(log_{2}(X)) time using range tree,
where X is the number of elements in the data structure. Here upper bound of X is 3^{(N/2)}.
The total complexity of this approach will be
O(3^{(N/2)} × log_{2}(3^{(N/2)})) ~ O(3^{(N/2)} × **N**) which is sufficient for test set 2.

Test Data

We recommend that you practice debugging solutions without looking at the test data.