Thanks to everyone who participated!

**Cast**

Problem A (Product Triplets): Written by Akashdeep Nain and prepared by Satyaki Upadhyay.

Problem B (Combining Classes): Written by and prepared by Jonathan Irvin Gunawan.

Problem C (Cave Escape): Written by Zhang Chen and prepared by Kevin Tran.

Solutions, other problem preparation, reviews and contest monitoring by Akashdeep Nain, Gary Sham, Ian Tullis, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu and Satyaki Upadhyay.

Analysis authors:

- Product Triplets: Jonathan Irvin Gunawan
- Combining Classes: Jonathan Irvin Gunawan
- Cave Escape: Himanshu Jaju

Given **N** integers **A**_{1}, **A**_{2}, ...,
**A**_{N}, count the number of triplets (x, y, z)
(with 1 ≤ x < y < z ≤ **N**) such that at least one of the following is true:

**A**_{x}=**A**_{y}×**A**_{z}, and/or**A**_{y}=**A**_{x}×**A**_{z}, and/or**A**_{z}=**A**_{x}×**A**_{y}

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each begins with one line containing an integer **N**: the number of integers in array
**A**. The second line consists of **N** integers **A**_{i}; the i-th of these is
the value of the i-th integer, as described above.

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 triplets satisfying the
condition given in the problem statement.

1 ≤ **T** ≤ 30.

Time limit: 40 seconds per test set.

Memory limit: 1 GB.

0 ≤ **A**_{i} ≤ 2 × 10^{5}, for all i.

3 ≤ **N** ≤ 200.

3 ≤ **N** ≤ 7000.

Sample Input

4 6 5 2 4 6 3 1 6 2 4 8 16 32 64 3 1 1 1 3 200000 200000 200000

Sample Output

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

In Sample Case #1, the only triplet satisfying the condition given in the problem statement is (2, 4, 5). The triplet is valid since the second, fourth, and fifth integers are 2, 6, and 3, and 2 × 3 = 6.

In Sample Case #2, the six triplets satisfying the condition given in the problem statement are: (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (2, 3, 5), (2, 4, 6).

In Sample Case #3, make sure you only count the triplet (1, 2, 3) once.

In Sample Case #4, there is no triplet satisfying the condition given in the problem statement since the product of any pair of integers in the array will not be in the array.

Supervin is teaching **N** classes, which are numbered from 1 to **N**. After giving his
most recent exam, he noticed that in each of his classes, the test scores of his students form a
sequence of consecutive integers. Therefore, Supervin can summarize the scores for the i-th class
as two integers **L**_{i} and **R**_{i}. This means that the i-th class has
**R**_{i} - **L**_{i} + 1 students, and for each x (**L**_{i}
≤ x ≤ **R**_{i}), there is exactly one student with score x.

Supervin would like to combine the scores from the students from all of his classes and sort the
scores in non-increasing order. He has **Q** questions (numbered from 1 to **Q**) about this
list; for the i-th question, he wants to know what the **K**_{i}-th highest score is.
(If **K**_{i} is greater than the number of students, then the answer for the i-th
question is 0.)

Can you help Supervin answer all of his questions? Since there may be many answers, instead of
outputting all of them, output proof that you have answered them: the sum of
(S_{i} × i) for all 1 ≤ i ≤ **Q**, where S_{i} is the answer to the
i-th question.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case contains four lines. The first line contains two integers **N** and **Q** as
described above. The next three lines each contain six integers in the following format,
respectively:

**X**_{1}**X**_{2}**A**_{1}**B**_{1}**C**_{1}**M**_{1}**Y**_{1}**Y**_{2}**A**_{2}**B**_{2}**C**_{2}**M**_{2}**Z**_{1}**Z**_{2}**A**_{3}**B**_{3}**C**_{3}**M**_{3}

We define:

**X**_{i}= (**A**_{1}×**X**_{i - 1}+**B**_{1}×**X**_{i - 2}+**C**_{1}) modulo**M**_{1}, for i = 3 to**N**.**Y**_{i}= (**A**_{2}×**Y**_{i - 1}+**B**_{2}×**Y**_{i - 2}+**C**_{2}) modulo**M**_{2}, for i = 3 to**N**.**Z**_{i}= (**A**_{3}×**Z**_{i - 1}+**B**_{3}×**Z**_{i - 2}+**C**_{3}) modulo**M**_{3}, for i = 3 to**Q**.

**L**_{i}= min(**X**_{i},**Y**_{i}) + 1, for i = 1 to**N**.**R**_{i}= max(**X**_{i},**Y**_{i}) + 1, for i = 1 to**N**.**K**_{i}=**Z**_{i}+ 1, for i = 1 to**Q**.

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 sum of (S_{i} × i)
for all 1 ≤ i ≤ **Q**, where S_{i} is the answer to the i-th question.

1 ≤ **T** ≤ 100.

Time limit: 180 seconds per test set.

Memory limit: 1 GB.

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

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

0 ≤ **B**_{i} < **M**_{i}, for all i.

0 ≤ **C**_{i} < **M**_{i}, for all i.

0 ≤ **X**_{1} < **M**_{1}.

0 ≤ **X**_{2} < **M**_{1}.

0 ≤ **Y**_{1} < **M**_{2}.

0 ≤ **Y**_{2} < **M**_{2}.

0 ≤ **Z**_{1} < **M**_{3}.

0 ≤ **Z**_{2} < **M**_{3}.

1 ≤ **M**_{i} ≤ 10^{9}, for all i.

**Q** = 1.

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

Sample Input

2 5 1 3 1 4 1 5 9 2 7 1 8 2 9 4 8 15 16 23 42 7 1 2 3 4 5 6 31 1 3 4 5 5 17 2 2 1 3 2 100

Sample Output

Case #1: 7 Case #2: 28

In Sample Case #1, the generated arrays **X**, **Y**, **Z** are:

**X**= [3, 1, 3, 0, 8].**Y**= [2, 7, 7, 2, 6].**Z**= [4].

**L**= [3, 2, 4, 1, 7].**R**= [4, 8, 8, 3, 9].**K**= [5].

Sample Input

2 5 5 3 1 4 1 5 9 2 7 1 8 2 9 4 8 15 16 23 42 1 2 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 2

Sample Output

Case #1: 39 Case #2: 1

In Sample Case #1, every parameter is the same as Sample Case #1 except the value of **Q**.
Therefore, the values of **L** and **R**, and the students' scores for all classes combined
are still the same as Sample Case #1. However, the queries are now **K** = [5, 9, 40, 23, 12].
The students with the 5th, 9th, and 12th highest scores have scores of 7, 6, and 4, respectively.
Since there are only 20 students, the 23rd and 40th students do not exist. Therefore,
S = [7, 6, 0, 0, 4] and the answer is
7 × 1 + 6 × 2 + 0 × 3 + 0 × 4 + 4 × 5 = 7 + 12 + 20 = 39.

In Sample Case #2, the generated arrays **X**, **Y**, **Z** are:

**X**= [0].**Y**= [0].**Z**= [0, 1].

**L**= [1].**R**= [1].**K**= [1, 2].

Mr. Raven is stuck in a cave represented by a matrix of **N** rows and **M** columns, where
rows are numbered from 1 to **N** from top to bottom, and columns are numbered from 1 to **M**
from left to right. The cell at the i-th row and the j-th column is denoted by (i, j). Mr. Raven
is currently at the cell (**S _{R}**,

Some cells of the cave may contain obstacles. Mr. Raven cannot step into a cell
that has an obstacle.

Other cells may contain traps. The first time that Mr. Raven enters a cell with a trap, he must
spend a number of energy points equal to the strength of the trap. If he has fewer energy points
than needed, he cannot enter the cell.

Moreover, some other cells may contain potions. The first time that Mr. Raven enters a cell with a
potion, he gains energy points equal to the strength of the potion.

Mr. Raven initially has **E** energy points. He can move between cells that share an edge
(not just a corner). On the exit cell, Mr. Raven can choose not to exit the cave and continue to
explore the cave if he wants to. Can you help him find the maximum number of energy points he can
have when he exits the cave, if it is possible to do so?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case consists of one line with seven integers **N**, **M**, **E**,
**S _{R}**,

- 0: represents an empty cell.
- -100000: represents a cell with an obstacle.
- an integer between -99999 and -1 (both inclusive): represents a trap with strength -
**V**._{ij} - an integer between 1 and 99999 (both inclusive): represents a potion with strength
**V**._{ij}

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 energy points that Mr.
Raven can have when he reaches the exit of the cave. If it is not possible for Mr. Raven to reach
the exit, output `-1`

.

1 ≤ **T** ≤ 100.

Time limit: 120 seconds per test set.

Memory limit: 1 GB.

1 ≤ **N** ≤ 100.

1 ≤ **M** ≤ 100.

0 ≤ **E** ≤ 100000.

1 ≤ **S _{R}** ≤ N.

1 ≤

1 ≤

1 ≤

(

-100000 ≤

At most 15 cells have -100000 <

There are no cells that have **V _{ij}** > 0. (There are no potions in the cave.)

No additional constraints.

Sample Input

2 4 4 100 1 1 4 4 0 0 0 0 0 0 0 0 0 0 0 -100000 0 0 -100000 0 2 2 100 1 1 2 2 0 0 0 0

Sample Output

Case #1: -1 Case #2: 100

In Sample Case #1, it is not possible for Mr. Raven to reach the exit.

In Sample Case #2, there are no traps and no potions, which means Mr. Raven can reach exit and no matter what path he follows his energy will stay unchanged.

Sample Input

1 8 8 250 7 1 1 7 -100000 -100000 -100000 -100000 -100000 -100000 0 -100000 -100000 0 -100000 0 -400 0 0 -100000 -100000 100 -300 0 -100000 -300 -100000 -100000 -100000 0 -100000 500 -100000 250 0 -100000 -100000 -200 -100000 -100000 -100000 -100000 -100 -100000 -100000 0 -100000 0 0 50 50 -100000 0 0 -100 0 -100000 50 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000

Sample Output

Case #1: 250

In Sample Case #1, the cave is as depicted in the following image where

- A cell with a positive integer x represents a potion with strength x.
- A cell with a negative integer y represents a trap with strength -y.
- Mr. Raven's initial position is in the cell with "You are here" text.

In this case, one of the optimal ways to reach the exit with maximum energy points is to

- Start with 250 energy points.
- Go to and destroy the trap at the cell (7, 3). 150 energy points remaining.
- Collect all three potions located at positions (6, 6), (6, 7) and (7, 6). 300 energy points remaining.
- Go to an destroy the trap at the cell (5, 7). 200 energy points remaining.
- Collect the potion at the cell (4, 6). 450 energy points remaining.
- Go to and destroy the trap at the cell (5, 2). 250 energy points remaining.
- Collect the potion at the cell (3, 2). 350 energy points remaining.
- Go to and destroy the trap at the cell (3, 3). 50 energy points remaining.
- Collect the potion at the cell (4, 4). 550 energy points remaining.
- Go to and destroy the trap at the cell (3, 6) and exit with 250 energy points remaining.

The Small dataset can be solved by complete search. We can check for each possible triplet
(x, y, z) (with 1 ≤ x < y < z ≤ **N**) and check whether at least either one of
**A**_{x}, **A**_{y}, or **A**_{z} is the product of the other
two. Each time we get a valid triplet, we increment our answer variable by one.

Since **N** ≤ 200 for this dataset, an O(**N**^{3}) time solution will run within
the time limit.

Let us ignore indices i where **A**_{i} = 0 for the time being. In other words, let us
assume that **A**_{i} > 0 for all i.

We can observe that for any three positive integers a, b, and c, if a × b = c, then
a ≤ c and b ≤ c. Therefore, if we sort **A** in nondecreasing order, for each triplet
(x, y, z) (with 1 ≤ x < y < z ≤ **N**), we only need to check whether
**A**_{x} × **A**_{y} = **A**_{z}. However, doing this
naively will still be an O(**N**^{3}) time solution.

We can optimize this solution by computing the number of z satisfying y < z and
**A**_{x} × **A**_{y} = **A**_{z} for each pair (x, y) in
constant time. To do this, we can store the number of occurrences of each number in **A** in a
hashmap.

If we design our nested loop such that we have y = {**N** .. 1} as our outer loop (and
x = {y - 1 .. 1} as our inner loop), then we can update our hashmap for **A**_{y} just
before we decrement the value of y. This is to make sure that our hashmap only contains the
elements with indices larger than the current value of y. In other words, the algorithm looks
something like:

```
sort(A)
ans = 0
occurrences = hashmap()
for y : {N .. 1}
for x : {y - 1 .. 1}
ans = ans + occurrences.count(A[x] * A[y])
occurrences.update(A[y], occurrences.get(A[y]) + 1)
```

We should not forget that our algorithm so far ignores those indices i where
**A**_{i} = 0. Suppose there are Z such indices (i.e., there are Z zeroes in **A**).
We can make C(Z, 3) triplets using three zeroes, and C(Z, 2) × (**N** - Z) triplets using
two zeroes and one non-zero.

Therefore, we get our final answer by summing the value of `ans`

from our pseudocode,
as well as C(Z, 3) and C(Z, 2) × (**N** - Z). This solution runs in
O(**N**^{2}) time.

Test Data

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

Let us define a function f(x) as the number of students scoring more than or equal to x. We can
compute f(x) in O(**N**) time by iterating through all classes.

Therefore, we can use binary search to find the largest x that satisfies f(x) ≥ **K**, which
is the score of the **K**-th highest score. This solution runs in
O(**Q** × **N** × log(10^{9})) time.

We can solve the Large dataset by compressing the scores first. That is, we map the existing
values of **L**_{i} and **R**_{i} onto a range [1, D], where D is the number
of distinct values in **L**_{i} and **R**_{i}. After compressing the scores,
we can assume that the students' scores are between 1 and 2**N**.

For each possible score x, let cnt(x) be the number of students with score x. We can compute the
values for all cnt(x) in O(**N** log(**N**)) using a range-update point-query data structure
such as a segment tree. If we compute the suffix sum (similar to
prefix sum, but we cumulate the sum
backwards) of cnt(x), we will get the number of students scoring more than or equal to x, which is
f(x).

Therefore, just as in our solution for the Small dataset, we can use binary search to find the
largest x that satisfies f(x) ≥ **K**. However, note that the answer is not exactly x, since
we compressed the scores earlier. The exact details of the implementation are left as an exercise.

This solution runs in O((**N** + **Q**) log **N**) time.

Test Data

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

Since there are no available potions in this dataset, we cannot increase our energy points and
hence we are looking for a path with the smallest sum of traps which leads us to the exit. We can
consider the cells of the grid as the vertices of our graph and moves between adjacent cells as
the edges, with the weight of an edge being the absolute value of the destination cell. Running
Dijkstra's algorithm on this graph gives us the path with the smallest sum of traps to reach
the exit in O(**NM** * log(**NM**)) time.

We can observe that whenever are potions that we can take without going through traps, we should always take them all before going through a trap. After that, we have two recursive choices :

- Go to the exit if it is reachable without going through a trap.
- Go through a trap cell which is reachable without going through any other trap. This choice can help us get more potions or help us reach the exit cell. After we choose to go through a trap cell, we should again take all potions that we can reach without going through an unvisited trap, and then repeat the choice above.

Let C_{T} be the count of traps in our test case. A naive recursive solution
based on the above would be of the order of O(**NM** * C_{T}!).

Observe that for a chosen subset of traps, all orderings of this subset have the same energy
points (after going through all the traps), the same set of reachable unvisited traps and the same
reachability of the exit cell. We can precompute these values by doing a graph search (BFS / DFS)
on all 2^{CT} subsets. To find the order of visiting the traps, we can use
dynamic programming along with bitmasks. For every mask of traps, we can choose to go to the
next unvisited reachable trap if its cost is not greater than our current energy points, or go to
the exit cell if it is reachable and take the choice that maximizes our answer.

The time complexity for precomputation is O(**NM** * 2^{CT}) and the
time complexity of finding the ordering using dynamic programming is
O(2^{CT} * C_{T}).

for every subset i in 2^{CT}subsets precompute : E_{i}:= Energy points left after visiting traps in subset i R_{i}:= Reachable unvisited traps after visiting traps in subset i Exit_{i}:= Denotes if exit cell is reachable from given subset of visited traps def MaxEnergy(mask) { ret := -1 // Go to exit if it is reachable if Exit_{mask}= True : ret := E_{mask}// Go to an unvisited reachable trap for i in R_{mask}: if TrapCost_{i}≤ E_{mask}: ret := max(ret, MaxEnergy(mask | 2^{i})) return ret }

Test Data

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