Thank you for participating in our second round for 2019. The first problem, *Building Palindromes*,
required an ad-hoc reasoning around optimal decisions and optimizing the implementation via precomputation.
The second problem, *Energy Stones*'s solution was based on dynamic programming. The last problem, *Diverse Subarray*
was a data structures problem requiring some nice observations.

**Cast**

Building Palindromes: Written by Bartosz Kostka and prepared by Sadia Atique.

Energy Stones: Written by Asim Krishna Prasad and prepared by Kunal Jain.

Diverse Subarray: Written by Himanshu Jaju and prepared by Sadia Nahreen.

Solutions, other problem preparation, reviews and contest monitoring by Akashdeep Nain, Anushi Maheshwari, Bir Bahadur Khatri, Darcy Best, Himanshu Jaju, Ian Tullis, Kevin Tran, Kunal Jain, Lalit Kundu, Lizzie Esapiro, Raihat Zaman Neloy, Sadia Atique, Sandeep Mohanty, Xinxing Jiang, and Yang Xiao.

Analysis authors:

- Building Palindromes: Sadia Atique
- Energy Stones: Max Ward
- Diverse Subarray: Max Ward

Anna has a row of **N** blocks, each with exactly one letter from `A`

to `Z`

written on it.
The blocks are numbered 1, 2, ..., **N** from left to right.

Today, she is learning about palindromes.
A palindrome is a string that is the same written forwards and backwards.
For example, `ANNA`

, `RACECAR`

, `AAA`

and `X`

are all palindromes, while
`AB`

, `FROG`

and `YOYO`

are not.

Bob wants to test how well Anna understands palindromes, and will ask her **Q** questions.
The i-th question is: can Anna use all of the blocks numbered from **L _{i}** to

Please help Anna by finding out how many of Bob's questions she can answer "yes" to.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case starts with a line containing the two integers **N** and **Q**, the number of blocks and the number of questions, respectively.
Then, another line follows, containing a string of **N** uppercase characters (`A`

to `Z`

).
Then, **Q** lines follow. The i-th line contains the two integers **L _{i}** to

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 questions Anna can answer "yes" to.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.
1 ≤ **L _{i}** ≤

1 ≤ **N** ≤ 20.

1 ≤ **Q** ≤ 20.

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

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

Sample Input

2 7 5 ABAACCA 3 6 4 4 2 5 6 7 3 7 3 5 XYZ 1 3 1 3 1 3 1 3 1 3

Sample Output

Case #1: 3 Case #2: 0

In Sample Case #1, **N** = 7 and **Q** = 5.

- For the first question, Anna must use the blocks
`AACC`

. She can rearrange these blocks into the palindrome`ACCA`

(or`CAAC`

). - For the second question, Anna must use the blocks
`A`

. This is already a palindrome, so she does not need to rearrange them. - For the third question, Anna must use the blocks
`BAAC`

. These blocks cannot be rearranged into a palindrome. - For the fourth question, Anna must use the blocks
`CA`

. These blocks cannot be rearranged into a palindrome. - For the fifth question, Anna must use the blocks
`AACCA`

. She can rearrange these blocks to form the palindrome`ACACA`

(or`CAAAC`

).

In Sample Case #2, **N** = 3 and **Q** = 5. For the first question, Anna must use the blocks `XYZ`

to create a palindrome.
This is impossible, and since the rest of Bob's questions are the same as the first one, the answer is 0.

Duda the rock monster lives in the enchanted forest and has collected **N** *energy stones* for lunch.
Since he has a small mouth, he eats energy stones one at a time.
Some stones are tougher than others! The i-th stone takes him **S _{i}** seconds to eat.

Duda eats energy stones to get *energy*.
Different stones give him different amounts of energy. Furthermore, the stones lose energy over time.
The i-th stone initially contains **E _{i}** units of energy and will lose

What is the largest amount of energy Duda could receive from eating his stones?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case starts with a line containing the integer **N**, the number of energy stones Duda has.
Then, there are **N** more lines, the i-th of which contains the three integers **S _{i}**,

`Case #x: y`

, where `x`

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

is the maximum amount of energy Duda could
receive from eating stones.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **N** ≤ 100.

1 ≤ **S _{i}** ≤ 100.

1 ≤

0 ≤

All stones take the same amount of time to eat. That is: **S _{i}** =

There are no additional constraints beyond the general Limits.

Sample Input

2 3 10 4 1000 10 3 1000 10 8 1000 2 10 2 0 10 3 0

Sample Output

Case #1: 8 Case #2: 5

In Sample Case #1, there are **N** = 3 stones. No matter which stone Duda eats, the other two will have no energy left once he is done eating. So he should eat the third stone, giving him 8 units of energy.

Sample Input

2 4 20 10 1 5 30 5 100 30 1 5 80 60 2 12 300 50 5 200 0

Sample Output

Case #1: 105 Case #2: 500

In Sample Case #1, there are **N** = 4 stones. One possible order Duda can eat stones is:

- Eat the fourth stone. This takes 5 seconds and gives him 80 units of energy.
- Eat the second stone. This takes 5 more seconds and gives him 5 units of energy (the second stone started with 30 energy, and over 5 seconds, has lost 25 units of energy).
- Eat the third stone. This takes 100 more seconds and gives him 20 units of energy (the third stone started with 30 energy, and over 10 seconds, has lost 10 units of energy).
- Eat the first stone. This takes 20 more seconds and gives him 0 units of energy (the first stone started with 10 units of energy, and over 110 seconds, has lost all of its energy).

In Sample Case #2, there are **N** = 2 stones. Duda can:

- Eat the first stone. This takes 12 seconds and gives him 300 units of energy.
- Eat the second stone. This takes 5 seconds and gives him 200 units of energy (the second stone does not lose any energy over time!).

Vanity has **N** trinkets on her shelf, numbered 1, 2, ..., **N** from left to right.
Trinkets come in different types, which are denoted by positive integers.
The i-th trinket on her shelf is of type **A _{i}**.

She is going to see her family overseas today and would like to bring as many trinkets as she can.
However, since she is in a hurry, Vanity must take a consecutive interval of trinkets.
Formally, Vanity selects two indices, *l* and *r*, and takes all of the trinkets numbered *l*, *l*+1, ..., *r*-1, *r*.
Also, due to tax rules, airport security will throw away *all* trinkets of a type if Vanity has more than **S** of that type in the chosen interval.

For example, suppose that **S** = 2, and Vanity brings six trinkets:
one of type 0, two of type 1, and three of type 2. She will be allowed to
keep the trinket of type 0 and both trinkets of type 1, but she will lose
*all* of the trinkets of type 2!

Vanity needs to choose *l* and *r* such that she can take the maximum number of trinkets for her
family. What is the maximum number of trinkets she can bring?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
The first line of each test case contains the two integers **N** and **S**, the number of
trinkets, and the maximum number of trinkets allowed of a single type, respectively.
The second line contains **N** integers. The i-th integer gives **A _{i}**, the
type of the i-th trinket.

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 maximum number of trinkets that Vanity can bring to her family.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

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

1 ≤

1 ≤ **N** ≤ 1000.

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

Sample Input

4 6 2 1 1 4 1 4 4 8 1 1 2 500 3 4 500 6 7 10 1 100 200 8 8 8 8 8 300 400 100 12 2 40 50 1 1 1 60 70 2 2 2 80 90

Sample Output

Case #1: 4 Case #2: 6 Case #3: 4 Case #4: 6

In Sample Case #1, Vanity should choose *l* = 2 and *r* = 5. This allows her to take 4 trinkets to the airport of types 1, 4, 1 and 4.
None of them are thrown away by airport security, so she is able to bring 4 trinkets to her family.

In Sample Case #2, Vanity should choose *l* = 1 and *r* = 8. This allows her to take all 8 trinkets to the airport.
Her trinkets of type 500 are thrown away since she has more than **S** = 1 of them, so she is able to bring a total of 6 trinkets to her family.

In Sample Case #3, Vanity should choose *l* = 1 and *r* = 9. This allows her to take 9 trinkets to the airport of types 100, 200, 8, 8, 8, 8, 8, 300 and 400.
Her trinkets of type 8 are thrown away since she has more than **S** = 1 of them, so she is able to bring a total of 4 trinkets to her family.

In Sample Case #4, Vanity should choose *l* = 1 and *r* = 12. This allows her to take all 12 trinkets to the airport.
Her trinkets of type 1 and 2 are thrown away since she has more than **S** = 2 of each of them, so she is able to bring a total of 6 trinkets to her family.

**Note**: We do not recommend using interpreted/slower languages for this problem.

For each query[**L**, **R**], we have to figure out if it is possible to make a palindrome
from substring[**L**, **R**] of the original block string.

For any substring, we can create all possible permutations of it and check if any of those
is a palindrome. For a substring of length *l*, in the worst case, there
would be Factorial(*l*) permutations, and
to check if a string of length *l* is palindrome is O(*l*). So the cost of each query
would be O(**N***Factorial(**N**)) and thus wouldn't fit within the time limit.

One important observation is that in a palindrome, at most one character can appear odd number of
times. If more than one character appears odd number of times in a string, it is impossible to
rearrange that string to form a palindrome.

If all characters in a string are present even times, we can just divide the characters into two
identical sets. Then we can make two strings with those two sets such that one string is the reverse
of the other one. Finally concatenate them to get a palindrome.

If we have only one character let's say *x*, which is present odd number of times,
we can set aside one *x*. Then we get a set of character where all characters are present
even number of times, and we can construct a palindrome in somewhat similar way as described above,
this time we can just put the *x* in between those two strings.

For each query, we can count the frequencies of all characters in the substring and decide
if it is possible to make a palindrome or not. The complexity of solving each query in this
approach is the length of the substring, which is O(**N**). Total complexity of this approach is
O(**N** × **Q**), which will be sufficient for test set 1.

We need to count the frequencies of each characters in a query substring, but can we make the counting
of frequencies faster?

Notice that, if we calculate prefix sum of frequencies for each character on the whole input string,
we can get the frequency of any character in any given substring in O(1) time.

In this approach, the time required to compute the prefix sum of the frequencies for each character
is O(**N**) and hence O(**N** × |character set|) for all. And for each query substring,
we can check parity of the frequency for each of the characters in O(|character set|) time.
So for **Q** queries, the overall complexity of this approach is
O((**N** + **Q**) × |character set|), which is sufficient for test set 2.

Test Data

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

For this test set, it is guaranteed that **S**_{i} = **S**_{j} for all i, j.
For simplicity, we will assume that we never eat a stone with zero energy.
Consider two energy stones i and j that will be eaten back-to-back.
If **L**_{i} > **L**_{j} then we should eat i before j.
This is because stone i loses energy faster than j, so taking it first will result in a smaller
overall loss of energy.

Thus, no matter which set of energy stones are eaten, that set should be eaten in non-increasing
value of **L**_{i}. So we should first sort the stones by **L**_{i} and then
the only decision to be made is which stones should be eaten and which should not be eaten.
This reduces the problem to a
0/1 Knapsack problem. This can be
solved with dynamic programming.

Define `max_energy(time, i)`

as the maximum total energy that can be achieved given
the current time and considering only the suffix of energy stones sorted in decreasing
**L**_{i} from i to **N**. The
recurrence relation for this function considers two cases. Either take the i-th energy stone
(with its energy adjusted by the time), or do not take it. So, `max_energy(time, i)`

is the maximum of:

- max_energy(time+
**S**_{i}, i+1) +max(0,**E**_{i}-**L**_{i}time) - max_energy(time,i+1)

We will need to find a different way to order the energy stones to solve Test set 2. As before,
consider two energy stones i and j assuming that we can take both i and j without either going to
zero energy. We know that **S**_{i} might not equal **S**_{j}. However,
there is an ordering for taking both i and j that is always optimal. Observe that
**S**_{i}**L**_{j} is the total loss of energy if i is used first.
Likewise, **S**_{j}**L**_{i} is the loss if j is used first. Thus, if
**S**_{i}**L**_{j} < **S**_{j}**L**_{i} then
taking i first leads to a smaller overall loss of energy.
It may not be obvious that we should always take i before j even if it leads to a smaller loss of
energy. This is because there may be other stones between i and j in some potential ordering.
However, if i and j are adjacent in some ordering, then we will achieve more energy by
swapping them if
**S**_{i}**L**_{j} > **S**_{j}**L**_{i}.
Applying this rule iteratively will eventually sort the stones.
Therefore, this rule defines an ordering on our energy stones.

Formally, suppose for a contradiction, we have an optimal solution that eats X stones in the order
P_{1}, P_{2}, ..., P_{X}, where each stone gives Duda a positive amount of energy,
but there exists an i such that
**S**_{Pi}**L**_{Pi+1} > **S**_{Pi+1}**L**_{Pi}.
If we swap the order we eat these two stones, we gain exactly **S**_{Pi}**L**_{Pi+1} more energy
and lose at most **S**_{Pi+1}**L**_{Pi} (we may lose less than that, if the stone's energy drops to zero).

Since we assumed that **S**_{Pi}**L**_{Pi+1} > **S**_{Pi+1}**L**_{Pi},
this would increase the amount of energy Duda gains, which contradicts the assumption that
this is an optimal solution.

Thus, we can use the dynamic programming solution from Test set 1 to solve Test set 2 with the same time complexity.

The reader may have noticed that this sort order is equivalent to comparing fractions; it is
the same as sorting by **S**_{i}/**L**_{i}. However, one must be careful
when **L**_{i}=0.

Test Data

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

Consider finding the optimal solution that is a prefix of the input. That is, let us only consider
taking ranges of trinkets [1,r] for any r. This reduces the problem to finding
prefix sum maximums. For example, consider this sequence of trinkets:

*1, 1, 2, 1, 3, 2, 3, 2, 2 *

Assume that **S**=2.

The first and second occurrence of a type can be modeled as a +1 event since we can take the
trinkets. The **S**+1th occurrence can be a -**S** event, since now we cannot take any
trinkets of that type. Finally, any further occurrence of that type can be a +0 since we
still cannot take them.
Thus, we have the following events:

*+1, +1, +1, -2, +1, +1, +1, -2, +0 *

A prefix sum ending at index r in our events corresponds to the score for taking the
subarray [1,r]. This idea can be generalized to any value of **S**, since all events
until the **S**+1th can be +1 events.

A naive algorithm can be realized using the above strategy.
It can be applied to each potential left point (instead of always starting at 1).
This explicitly considers every possible range [l,r] and computes the number of
trinkets. The events can be calculated by keeping track of how many times each type has occurred
while sweeping across the trinkets and keeping a running sum of events. The count of types can be
handled with a frequency table. Any map from type to count can implement this, for example, an
array or hashtable. The strategy uses O(**N**) time to process the solution starting at a
particular left point. There are O(**N**) left points. Thus, the time complexity is
O(**N**^{2}). This is sufficient for Test set 1.

The previous algorithm will not be fast enough for the Test set 2. Observe that the events for
the lth left point are closely related to those for the l+1th left point. In
particular, only events corresponding to the type of the trinket at index l change. In
fact, only the -**S** for that type changes. It moves over to the next +0 event for that type
if it exists. The previous -**S** event becomes a +1. This means that the events only change at
a constant number of places.

Using this observation, we can think about this as a data structure problem. We require a data structure that supports two operations:

- Change the value at an index.
- What is the maximum prefix sum?

Test Data

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