Round 1C started off with hundreds of submissions to problem A. Soon after, solutions to C-small started pouring in. Many contestants noticed the low point value of C-small and solved it with a quick brute force solution.

At the 25 minute mark, solutions to problem B began appearing at the top of the scoreboard. Burunduk1 took the lead, followed by wangyongliang and anton.akhi.

Problem C-large proved to be very difficult. It was a choice between risking a time-out with BigInteger and risking overflow with int64. After more than 100 contestants had attempted C-large unsuccessfully, meshanya was the first to solve it, 52 minutes into the contest, but had yet to start on problem B.

Burunduk1 followed a minute later with the second correct C-large and retook his first place. Ten minutes later, mystic solved C-large and grabbed second place. Soon after, yuhch123 submitted the 4th correct C-large (out of over 300 attempts by that point) and took 3rd.

The competition for top 1000 was fierce. The minimum score to advance ended up being 40, which meant solving at least problem A and both of the other smalls with at least 30 minutes left to go.

Congratulations to all 3000 advancers. Good luck in Round 2!

Cast

Problem A. *Square Tiles* Written and prepared by David Arthur.

Problem B. *Space Emergency* Written by Bartholomew Furrow and prepared by Jorge Bernadas Saragoza.

Problem C. *Perfect Harmony* Written by Onufry Wojtaszczyk and prepared by Igor Naverniouk.

Contest analysis presented by Jorge Bernadas Saragoza, Bartholomew Furrow and Onufry Wojtaszczyk.

Solutions and other problem preparation by Tomek Czajka, Stephen Fulwider, John Dethridge, Luka Kalinovcic and Kuang-che Wu.

You are selling beautiful geometric pictures. Each one consists of 1x1 square tiles arranged into a non-overlapping grid. For example:

.##.. .#### .#### .##..

Blue tiles are represented by '#' characters, and white tiles are represented by '.' characters. You do not use other colors.

Not everybody likes blue though, and some customers want you to replace all the blue tiles in your picture with red tiles. Unfortunately, red tiles only come in the larger 2x2 size, which makes this tricky.

You can cover any 2x2 square of blue tiles with a single red tile, and then repeat until finished. A red tile cannot overlap another red tile, it cannot cover white tiles, and it cannot go outside the picture. For example, you could add red tiles to the previous picture as follows:

./\.. .\//\ ./\\/ .\/..

Each red tile is represented here by a pair of '/' characters in the top-left and bottom-right corners, and a pair of '\' characters in the other two corners.

Given a blue and white picture, can you transform it into a red and white picture in this way?

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 **R** and **C**, the number of rows and columns in a picture. The next **R** lines each contain exactly **C** characters, describing the picture. As above, '#' characters represent blue tiles, and '.' characters represent white tiles.

For each test case, first output one line containing "Case #x:" where x is the case number (starting from 1).

If it is possible to cover the blue tiles with non-overlapping red tiles, output **R** lines each containing **C** characters, describing the resulting red and white picture. As above, red tiles should be represented by '/' and '\' characters, while white tiles are represented by '.' characters. If multiple solutions are possible, you may output any of them.

If the task is impossible, output a single line containing the text "Impossible" instead.

Memory limit: 1GB.

1 ≤ **T** ≤ 20.

1 ≤ **R** ≤ 6.

1 ≤ **C** ≤ 6.

Time limit: 30 seconds.

1 ≤ **T** ≤ 50.

1 ≤ **R** ≤ 50.

1 ≤ **C** ≤ 50.

Time limit: 60 seconds.

Sample Input

3 2 3 ### ### 1 1 . 4 5 .##.. .#### .#### .##..

Sample Output

Case #1: Impossible Case #2: . Case #3: ./\.. .\//\ ./\\/ .\/..

There's an emergency—in space! You need to send your fleet's flagship as quickly as possible from star 0 to star **N**, traveling through the other stars in increasing numerical order along the way (0→1→...→**N**). Your flagship normally travels at a speed of 0.5 parsecs per hour.

In addition to sending your flagship, you can order your engineers to build up to **L** speed boosters at different stars. Building a speed booster takes **t** hours, and all **L** speed boosters can be built in parallel. While your flagship travels from a star with a completed speed booster to the next star, its speed is 1 parsec per hour.

If a speed booster is completed at a star while your flagship is traveling from that star to the next one, your flagship will start moving faster as soon as the speed booster is completed.

How many hours does it take your flagship to get to star **N** if you build speed boosters to make it arrive as soon as possible?

The first line of the input gives the number of test cases, **T**. **T** lines follow. Each contains integers, **L**, **t**, **N** and **C**, followed by **C** integers **a _{i}**, all separated by spaces.

For example, with **N**=8, **C**=3, **a _{0}**=3,

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is a single integer: the number of hours it takes to reach star **N**. The answer is guaranteed to always be an integer.

1 ≤ **T** ≤ 100.

1 ≤ **C** ≤ 1000.

**C** ≤ **N**.

1 ≤ **a _{i}** ≤ 10

0 ≤

Memory limit: 1GB.

1 ≤ **N** ≤ 1000.

0 ≤ **L** ≤ 2.

Time limit: 30 seconds.

1 ≤ **N** ≤ 10^{6}.

0 ≤ **L** ≤ N.

Time limit: 60 seconds.

Sample Input

2 2 20 8 2 3 5 1 4 2 2 10 4

Sample Output

Case #1: 54 Case #2: 20

In the second case, we can build one speed booster. The distances between stars are [10, 4]. We build the speed booster on the first star. After 4 hours, our flagship has gone 2 parsecs and the speed booster is complete. It takes our flagship another 8 hours to get to star 1, then 8 more hours to get to star 2, our destination.

**Note:** This problem takes place in a universe where the speed of light is much higher than 1 parsec per hour, so we don't have to worry about special relativistic effects.

Jeff is a part of the great Atlantean orchestra. Each player of the orchestra has already decided what sound will he play (for the sake of simplicity we assume each player plays only one sound). We say two sounds are in harmony if the frequency of any one of them divides the frequency of the other (that's a pretty restrictive idea of harmony, but the Atlanteans are known to be very conservative in music). Jeff knows that the notes played by other players are not necessarily in harmony with each other. He wants his own note to improve the symphony, so he wants to choose his note so that it is in harmony with the notes all the other players play.

Now, this sounds simple (as all the frequencies are positive integers, it would be enough for Jeff to play the note with frequency 1, or, from the other side, the Least Common Multiple of all the other notes), but unfortunately Jeff's instrument has only a limited range of notes available. Help Jeff find out if playing a note harmonious with all others is possible.

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each test case is described by two lines. The first contains three numbers: **N**, **L** and **H**, denoting the number of other players, the lowest and the highest note Jeff's instrument can play. The second line contains **N** integers denoting the frequencies of notes played by the other players.

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either the string "NO" (if Jeff cannot play an appropriate note), or a possible frequency. If there are multiple frequencies Jeff could play, output the lowest one.

1 ≤ **T** ≤ 40.

Memory limit: 1GB.

1 ≤ **N** ≤ 100.

1 ≤ L ≤ H ≤ 10000.

All the frequencies are no larger than 10000.

Time limit: 30 seconds.

1 ≤ **N** ≤ 10^{4}.

1 ≤ **L** ≤ **H** ≤ 10^{16}

All the frequencies are no larger than 10^{16}

Time limit: 60 seconds.

Sample Input

2 3 2 100 3 5 7 4 8 16 1 20 5 2

Sample Output

Case #1: NO Case #2: 10

One solution for this problem would be to try to put red tiles in all possible ways over the blue tiles and see if at least one possibility leads to all the blue tiles being covered. However, this will not work in time because there are too many combinations to try.

To optimize the solution, you have to observe that if there is a solution, the top-most, left-most blue tile in the grid (that is, the left-most tile of all the blue tiles in the top row that contains any blue tiles) must be covered by the left-top corner of some red tile. This is because the tiles at its left and top are white (or non-existent), and so the red tile covering our blue tile cannot extend to the left or upwards of it. Based on this observation, we can solve the problem greedily by putting a red tile over the top-most, left-most blue tile in the only way it can be done. If for some blue tile it is impossible to cover it this way (because the red tile would cover some white tiles or extend outside the picture), then it's impossible to cover the whole board.

Note that as we are always sure that any red tile we put down is correct (if a solution exists at all), we can just modify the board on the fly, and thus at the same time check for solution existence and retrieve the answer. To illustrate that, here is a C++ function to cover all the blue tiles in a grid and return whether it was possible or not:

bool CoverTiles(vector<string>& grid) { const int m = (int)grid.size(), n = (int)grid[0].size(); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == '#') { for (int di = 0; di < 2; ++di) for (int dj = 0; dj < 2; ++dj) if (i + di < m && j + dj < n && grid[i + di][j + dj] == '#') grid[i + di][j + dj] = "/\\"[(di + dj) % 2]; else return false; } return true; }

Fun fact: the solution does not change if we drop the requirement that red tiles have to cover 2x2 squares of blue tiles - it is still valid if we allow the rotation and arbitrary positioning of the red tiles; the only condition that matters is that red tiles lie only on blue tiles (do not overlap, stick outside the picture or lie on white tiles) and all the blue tiles are covered in the end.

Test Data

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

In this problem, you have a series of edges to follow and you're given the option of shortening up to **L** of the edges by a factor of two. There's one catch: the shortening takes some time to take effect.

Fortunately, all possible shortenings take the same amount of time, so we can divide our edges into three categories:

- Edges that your flagship will pass before any speed boosters can be built.
- Edges whose speed boosters would finish
**while**your flagship is moving along the edge. - Edges whose speed boosters can be built before your flagship gets there.

Group 2 only has zero or one members, because we know exactly where your flagship will be when the speed boosters finish building.

Now we can decide how useful it is to build a speed booster on each edge. We never want to build speed boosters on group 1, because they won't help. For each edge in group 3, the benefit is length/2. For the edge in group 2, the benefit is (distance to the end of the edge from where your flagship will be when the speed booster finishes building)/2.

We choose the **L** most beneficial edges to build on; if there aren't **L** beneficial edges, we'll stop when we've built on all the beneficial edges. Then we compute the total benefit, subtract it from the total time to traverse the whole path, and voilà! The answer.

The way in which we specify edges in this problem is periodic: if the input is very large, then there must be a lot of edges with the same lengths. A clever solution could take advantage of the periodic nature to run very quickly, but the limits were small enough that this shouldn't be necessary; we actually specified the input in this way because it would make the input file smaller, not because we wanted to test that particular skill.

Test Data

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

This problem turned out to be very, very tricky, due to a number of cases to consider and the possibility of integer overflow. Thus, we will go over the solution with some care.

To solve the small data set for this problem, it is enough to iterate over all notes that can be played by Jeff, and for each of them check whether it is in harmony with all the other notes. Note that there are two cases to consider for each note - either its frequency has to divide the frequency of Jeff's note, or it has to be divisible by it.

For the large data set, this strategy will not be sufficient - there are too many notes that Jeff can play to check.

We will begin by sorting all the input frequencies. Now assume that the frequency of the note that Jeff will play (let us denote it by **F**) is somewhere between frequencies **f _{k}** and

To make any use of this information, we need to calculate all the LCMs of sets **f _{1}**, ...,

Let us recall that the GCD of two numbers **a** and **b** can be calculated using the Euclidean algorithm in O(log(**a + b**)) time. To calculate the LCM of two numbers, we use the formula LCM(**a**, **b**) = **a** * **b** / GCD(**a**, **b**). Using this, we can calculate all the needed GCDs and LCMs in O(**N**) GCD operations, inductively. For instance, having already calculated the first **k-1** LCMs, we calculate the **k**th as follows: LCM(**f _{1}**, ...,

Note that one can also calculate all the GCDs and LCMs directly, in O(**N**^{2}) GCD operations. With the limit of 10^{4} on GCD this should also run in time.

One final comment to make here is that when calculating the LCMs, we should be careful to avoid overflow. It may turn out that the LCM of some of the input frequencies does not fit into a 64-bit integer (in general, the LCM of 10^{4} numbers, each up to 16 digits, can have even 160,000 digits!). However, note that Jeff cannot play notes with frequency greater than 10^{16}, thus if the LCM of any numbers turns out to be greater than 10^{16} (or even greater than **H**) we can safely replace it by 10^{16} + 1 without changing the answer - Jeff will not be able to play a note with a frequency divisible by this LCM anyway. Thus, when we calculate the formula **a** * **b** / GCD(**a**, **b**) we should first divide any of the two numbers, say **a**, by the GCD, then check whether the resulting product exceeds **H** (e.g. by checking whether (**H** + 1) / **b** ≥ **a** / GCD(**a**, **b**), and perform the multiplication only if it does not.

Before going on, we should also consider that there are two special cases when the analysis above does not apply - when **F** divides all the input frequencies, and when **F** is divisible by all of them.

There are a number of ways to take care of them. For the first, the easiest is to add another note with frequency 1 to the input. This will not make Jeff's task harder, as any number is divisible by 1, and on the other hand will assure that **F** is always divisible by at least one of the numbers in the input.

For the upper bound, no analogous trick exists (there is no number that is divisible by any **F** Jeff might choose; one might consider the LCM of all the numbers that Jeff's instrument can play, but this is usually too large. Thus, if we fail to find a solution **F** lying between any two of the input frequencies, we have to consider this case separately. Fortunately, it is not complicated - if **C** is the LCM of all the input numbers, then the result will be the smallest multiple of **C** that is greater or equal **L**, provided it is no larger than **H**.

Notice that as we are looking for the lowest frequency Jeff can play, we can investigate the possibilities one by one - first check if there is a solution between **f _{1}** and

Now for the crux of the problem - how can we check (quickly) whether a solution is to be found between **f _{k}** and

Recall that if **F** is between **f _{k}** and

There are two more easy cases to consider. If the intervals [**L**, **H**] and [**C**, **D**] are disjoint, there is obviously no solution in this interval. If **C** lies in the interval [**L**, **H**] (and divides **D**, which we already checked), it is obviously the smallest solution in this interval, so we may safely return it.

Notice that there is at most one interval for which those easy (and in particular, constant time) checks will not suffice. Indeed, if for some **k** the intervals [**L**, **H**] and [**C**, **D**] are not disjoint, then for any subsequent interval [**C'**, **D'**] obtained for a different **k'** either **C'** lies in [**L**, **H**], or the two intervals are disjoint, as **L** ≤ **D** ≤ **f _{k+1}** ≤

Finally, we can concentrate on this one interval. We want to find the smallest number **F** in the interval [**L**, **H**] that divides **D** and is divisible by **C**. For this, it is enough to consider all the divisors of **D** and check them one-by-one. The divisors of **D** can be enumerated in time proportional to the square root of **D** - for each divisor **d**, either **d** or **D**/**d** is no larger than the square root of **D**, thus to find all the divisors we check all the numbers no larger than the square root, and if a number **d** divides **D**, we add both **d** and **D**/**d** to the list of divisors. This algorithm returns the divisors almost sorted, so it is easy to consider them in ascending order and find the first that both is divisible by **C** and falls into the interval [**L**, **H**].

This was not an easy problem, and required quite a lot of care and attention. Let us enumerate the steps, to wrap it up:

- Sort all the input frequencies (in O(
**N**log**N**) time) - Add 1 to the beginning of the list of inputs (in O(1) time :) )
- Calculate the prefix LCMs and suffix GCDs (in O(
**N**) GCD operations, each taking O(log**H**) time (as we do not consider results greater than**H**) - For each
**k**from 1 to**N**-1 check whether the appropriate LCM divides the appropriate GCD (if no, proceed to next interval); if the LCM falls into [**L**,**H**] (if yes, return the LCM) and whether the intervals [LCM, GCD] and [**L**,**H**] intersect (if no, proceed to the next interval). This takes constant time for each interval, so O(**N**) time in total. - If we are still analyzing this interval, find all the divisors of the GCD and check them one by one. This takes O(sqrt(
**H**)) time. - If no answer was found as yet, it remains to check the smallest multiple of the LCM of all the inputs that is greater or equal than
**L**. This is done in constant time.

There are other approaches possible to this problem, too. For instance, one may analyze all the divisors of the largest input frequency, and for each of them use binary search to find the interval that contains it and (in constant time, using precalculated LCMs and GCDs) check whether it is a correct solution. We encourage you to analyze the details of this approach yourself.

Test Data

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