Thank you for participating in Kick Start 2021 Round B!

**Cast**

Increasing Substring: Written by Himanshu Jaju and prepared by Eric Dong.

Longest Progression: Written by Vipin Singh and prepared by Bryan (Seunghyun) Jo.

Consecutive Primes: Written by Pablo Heiber and prepared by Nikhil Hassija.

Truck Delivery: Written by Sudarsan Srinivasan and prepared by Bartosz Kostka.

Solutions, other problem preparation, reviews and contest monitoring by Abhishek Saini, Akshay Mohan, Akul Siddalingaswamy, Amr Aboelkher, Aneesh D H, Ankit Goyal, Ankur Dua, Anson Ho, Anurag Singh, Anushi Maheshwari, Bao Nguyen, Bartosz Kostka, Bir Bahadur Khatri, Bohdan Pryshchenko, Bryan (Seunghyun) Jo, Cristhian Bonilha, Diksha Saxena, Dipjal Chhetri, Eric Dong, Gregory Yap, Himanshi Jain, Himanshu Jaju, Hsin-cheng Hou, Jakub Kuczkowiak, Janice Chui, Jared Gillespie, Kashish Bansal, Krists Boitmanis, Lizzie Sapiro Santor, Nikhil Hassija, Ossama Mahmoud, Pablo Heiber, Rahul Goswami, Ruoyu Zhang, Samiksha Gupta, Sarah Young, Sera Wang, Shweta Karwa, Subhasmita Sahoo, Sudarsan Srinivasan, Surya Upadrasta, Swapnil Gupta, Swapnil Mahajan, Teja Vardhan Reddy Dasannagari, Vaibhav Tulsyan, Vijay Krishan Pandey, Vikash Dubey, Vipin Singh, Viplav Kadam, Wajeb Saab.

Analysis authors:

- Increasing Substring: Swapnil Gupta
- Longest Progression: Gregory Yap
- Consecutive Primes: Ankit Goyal
- Truck Delivery: Krists Boitmanis

Your friend John just came back from vacation, and he would like to share with you a new property that he learned about strings.

John learned that a string $$$C$$$ of length $$$L$$$ consisting of uppercase English characters is strictly increasing if, for every pair of indices $$$i$$$ and $$$j$$$ such that $$$1 \le i \lt j \le L$$$ ($$$1$$$-based), the character at position $$$i$$$ is smaller than the character at position $$$j$$$.

For example, the strings `ABC`

and `ADF`

are strictly increasing,
however the strings `ACC`

and `FDA`

are not.

Now that he taught you this new exciting property, John decided to challenge you: given a string $$$\mathbf{S}$$$ of length $$$\mathbf{N}$$$, you have to find out, for every position $$$1 \le i \le \mathbf{N}$$$, what is the length of the longest strictly increasing substring that ends at position $$$i$$$.

The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow.

Each test case consists of two lines.

The first line contains an integer $$$\mathbf{N}$$$, representing the length of the string.

The second line contains a string $$$\mathbf{S}$$$ of length $$$\mathbf{N}$$$, consisting of uppercase English characters.

For each test case, output one line containing
`Case #$$$x$$$: $$$y_1$$$ $$$y_2$$$ ... $$$y_n$$$`

,
where $$$x$$$ is the test case number (starting from 1) and $$$y_i$$$ is the length of
the longest strictly increasing substring that ends at position $$$i$$$.

Memory limit: 1 GB.

$$$1 \le \mathbf{T} \le 100$$$.

Time limit: 20 seconds.

$$$1 \le \mathbf{N} \le 100$$$.

Time limit: 40 seconds.

$$$1 \le \mathbf{N} \le 2 \times 10^5$$$.

Sample Input

2 4 ABBC 6 ABACDA

Sample Output

Case #1: 1 2 1 2 Case #2: 1 2 1 2 3 1

In Sample Case #1, the longest strictly increasing substring ending at position $$$1$$$ is `A`

.
The longest strictly increasing substrings ending at positions $$$2$$$, $$$3$$$ and $$$4$$$ are
`AB`

, `B`

and `BC`

, respectively.

In Sample Case #2, the longest strictly increasing substrings for each position are
`A`

, `AB`

, `A`

, `AC`

, `ACD`

and `A`

.

In Kick Start 2020 Round E (you do not need to know anything about the previous problem to solve this one) Sarasvati learned about arithmetic arrays. An arithmetic array is an array that contains at least two integers and the differences between consecutive integers are equal. For example, $$$[9, 10]$$$, $$$[3, 3, 3]$$$, and $$$[9, 7, 5, 3]$$$ are arithmetic arrays, while $$$[1, 3, 3, 7]$$$, $$$[2, 1, 2]$$$, and $$$[1, 2, 4]$$$ are not.

Sarasvati again has an array of $$$\mathbf{N}$$$ non-negative integers. The $$$i$$$-th integer of the array is $$$\mathbf{A_i}$$$. She can replace at most one element in the array with any (possibly negative) integer she wants.

For an array $$$\mathbf{A}$$$, Sarasvati defines a subarray as any contiguous part of $$$\mathbf{A}$$$. Please help Sarasvati determine the length of the longest possible arithmetic subarray she can create by replacing at most one element in the original array.

The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow. Each test case begins with a line containing the integer $$$\mathbf{N}$$$. The second line contains $$$\mathbf{N}$$$ integers. The $$$i$$$-th integer is $$$\mathbf{A_i}$$$.

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 length of the longest
arithmetic subarray.

Time limit: 30 seconds.

Memory limit: 1 GB.

$$$1 \le \mathbf{T} \le 100$$$

$$$0 \le \mathbf{A_i} \le 10^{9}$$$.

$$$2 \le \mathbf{N} \le 2000$$$.

$$$2 \le \mathbf{N} \le 3 \times 10^{5}$$$ for at most $$$10$$$ test cases.

For the remaining cases, $$$2 \le \mathbf{N} \le 2000$$$.

Sample Input

3 4 9 7 5 3 9 5 5 4 5 5 5 4 5 6 4 8 5 2 0

Sample Output

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

In Sample Case #1, the whole array is an arithmetic array, thus the longest arithmetic subarray is the whole array.

In Sample Case #2, if Sarasvati changes the number at third position to $$$5$$$, the array will become $$$[5, 5, 5, 5, 5, 5, 4, 5, 6]$$$. The subarray from first position to sixth position is the longest arithmetic subarray.

In Sample Case #3, Sarasvati can change the number at the last position to $$$-1$$$, to get $$$[8, 5, 2, -1]$$$. This resulting array is arithmetic.

Ada has bought a secret present for her friend John. In order to open the present, Ada wants John to crack a secret code. She decides to give him a hint to make things simple for him. She tells him that the secret code is a number that can be formed by taking the product of two consecutive prime numbers, such that it is the largest number that is smaller than or equal to $$$\mathbf{Z}$$$. Given the value of $$$\mathbf{Z}$$$, help John to determine the secret code.

Formally, let the order of prime numbers $$$2, 3, 5, 7, 11, $$$ ... be denoted by $$$p_1, p_2, p_3, p_4, p_5, $$$ ... and so on. Consider $$$R_i$$$ to be the product of two consecutive primes $$$p_i$$$ and $$$p_{i+1}$$$. The secret code is the largest $$$R_j$$$ such that $$$R_j \le \mathbf{Z}$$$.

The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ lines follow.

Each line contains a single integer $$$\mathbf{Z}$$$, representing the number provided by Ada as part of
the hint.

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 secret code -
the largest number less than or equal to $$$\mathbf{Z}$$$ that is the product of two
consecutive prime numbers.

Time limit: 15 seconds.

Memory limit: 1 GB.

$$$1 \le \mathbf{T} \le 100$$$.

$$$6 \le \mathbf{Z} \le 2021$$$.

$$$6 \le \mathbf{Z} \le 10^9$$$.

$$$6 \le \mathbf{Z} \le 10^{18}$$$.

Sample Input

2 2021 2020

Sample Output

Case #1: 2021 Case #2: 1763

For Sample Case #1, the secret code is $$$2021$$$ because it is exactly the product of consecutive primes $$$43$$$ and $$$47$$$.

For Sample Case #2, the secret code is $$$1763$$$ because the product of $$$41$$$ and $$$43$$$ is $$$1763$$$ which is smaller than $$$2020$$$, but the product of $$$43$$$ and $$$47$$$ exceeds the given value of $$$2020$$$.

Charles is a truck driver in the city of Googleland. Googleland is built in form of a tree with $$$\mathbf{N}$$$ nodes where each node represents a city and each edge represents a road between two cities. The cities are numbered $$$1$$$ to $$$\mathbf{N}$$$. The capital of Googleland is city $$$1$$$. Each day Charles picks up a load of weight $$$\mathbf{W}$$$ in city $$$\mathbf{C}$$$ and wants to deliver it to city $$$1$$$ using the simple path (which is unique) between the cities. Each road $$$i$$$ has a toll which charges amount $$$\mathbf{A_i}$$$ if the weight of the load is greater than or equal to a load-limit $$$\mathbf{L_i}$$$.

Charles works for $$$\mathbf{Q}$$$ days, where for each day Charles will be given the starting city $$$\mathbf{C}$$$ and weight of the load $$$\mathbf{W}$$$. For each day find the greatest common divisor of all the toll charges that Charles pays for that day. If Charles did not have to pay in any of the tolls the answer is $$$0$$$.

The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow.

The first line of each test case contains the two integers $$$\mathbf{N}$$$ and $$$\mathbf{Q}$$$.

The next $$$\mathbf{N}-1$$$ lines describe the roads. $$$i$$$-th of these lines contains the four space separated integers $$$\mathbf{X}$$$, $$$\mathbf{Y}$$$, $$$\mathbf{L_i}$$$ and $$$\mathbf{A_i}$$$, indicating a road between cities $$$\mathbf{X}$$$ and $$$\mathbf{Y}$$$ with load-limit $$$\mathbf{L_i}$$$ and toll charge $$$\mathbf{A_i}$$$.

The next $$$\mathbf{Q}$$$ lines describe the queries. $$$j$$$-th of these lines contains the two space separated integers $$$\mathbf{C_j}$$$ and $$$\mathbf{W_j}$$$ representing the starting city and weight of the load on $$$j$$$-th day.

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

,
where $$$x$$$ is the test case number (starting from 1) and $$$y$$$
is a list of the answers for $$$\mathbf{Q}$$$ days in order, separated by spaces.

Memory limit: 1 GB.

$$$1 \le \mathbf{T} \le 100$$$.

$$$1 \le \mathbf{L_i} \le 2 \times 10^5$$$, for all $$$i$$$.

$$$1 \le \mathbf{A_i} \le 10^{18}$$$, for all $$$i$$$.

All $$$\mathbf{L_i}$$$ are distinct.

$$$2 \le \mathbf{C_j} \le \mathbf{N}$$$, for all $$$j$$$.

$$$1 \le \mathbf{W_j} \le 2 \times 10^5$$$, for all $$$j$$$.

It is guaranteed that given roads form a tree.

Time limit: 20 seconds.

$$$2 \le \mathbf{N} \le 1000$$$.

$$$1 \le \mathbf{Q} \le 1000$$$.

Time limit: 80 seconds.

$$$2 \le \mathbf{N} \le 5 \times 10^4$$$ and $$$1 \le \mathbf{Q} \le 10^5$$$ for at most $$$20$$$ test cases.

For the remaining cases, $$$2 \le \mathbf{N} \le 1000$$$ and $$$1 \le \mathbf{Q} \le 1000$$$.

Sample Input

2 7 5 2 1 2 4 2 3 7 8 3 4 6 2 5 3 9 9 2 6 1 5 7 1 5 7 5 10 5 8 4 1 6 1 7 6 3 2 1 2 2 10 3 2 3 5 3 2 3 3

Sample Output

Case #1: 1 4 0 5 7 Case #2: 10 5

In Sample Case #1

On the first day, Charles should pay toll charges in the roads between cities $$$(5,3), (3,2)$$$ and $$$(2,1)$$$. The answer will be $$$\gcd(9,8,4) = 1$$$.

On the second day, Charles should pay toll charges in the roads between cities $$$(3,2)$$$ and $$$(2,1)$$$. The answer will be $$$\gcd(8,4) = 4$$$.

On the third day, Charles need not pay toll charges in any of the cities. Thus, the answer will be $$$0$$$.

In Sample Case #2

On the first day, Charles should pay toll charges in the roads between cities $$$(2,1)$$$. The answer will be $$$10$$$.

On the second day, Charles should pay toll charges in the roads between cities $$$(3,2)$$$ and $$$(2,1)$$$. The answer will be $$$\gcd(5,10) = 5$$$.

A string $$$X$$$ of length $$$L$$$ is strictly increasing, if for every pair of indices $$$i$$$ and $$$j$$$ such that $$$1 \le i \lt j \le L$$$ ($$$1$$$-based), the character at position $$$i$$$ is smaller than the character at position $$$j$$$. Using this, we can say that $$$X_i \lt X_{i+1}$$$ for $$$1 \le i \lt L$$$. We can check this in $$$O(L)$$$ time complexity for string $$$X$$$.

There are $$$O(\mathbf{N}^{2})$$$ substrings of string $$$\mathbf{S}$$$ each of which can have length at most $$$\mathbf{N}$$$. We can iterate over each substring and check whether it is strictly increasing in $$$O(\mathbf{N})$$$ time. If a substring from $$$i$$$ to $$$j$$$ is strictly increasing, update the length of longest strictly increasing substring ending at index $$$j$$$ to $$$j-i+1$$$ if it is greater than the previous found length. The overall time complexity of the solution is $$$O(\mathbf{N}^3)$$$.

Consider the following example with string $$$bbcd$$$. There is only $$$1$$$ substring ($$$b$$$) ending at index $$$1$$$. Hence, the answer for index $$$1$$$ is $$$1$$$. There are $$$2$$$ substrings ($$$b$$$ and $$$ bb$$$) which end at index $$$2$$$. $$$bb$$$ is not strictly increasing string. Hence, the answer for index $$$2$$$ is $$$1$$$. There are $$$3$$$ substrings ($$$bbc$$$, $$$bc$$$, and $$$c$$$) ending at index $$$3$$$. $$$bbc$$$ is not strictly increasing as $$$b$$$ is repeated twice. $$$bc$$$ is the longest strictly increasing substring ending at index $$$3$$$. Hence, answer for index $$$3$$$ is $$$2$$$. There are $$$4$$$ substrings ($$$bbcd$$$, $$$bcd$$$, $$$cd$$$, and $$$d$$$) ending at index $$$4$$$. $$$bbcd$$$ is not strictly increasing as b is repeated twice. $$$bcd$$$ is the longest strictly increasing substring ending at index $$$4$$$. Hence, answer for index $$$4$$$ is $$$3$$$.

```
vector<
````int`> longestStrictlyIncreasingSubstring(string S) {
vector<`int`> answer(S.size(), 0);
for(`int` i = 0; i < S.size(); i++) {
for(`int` j = i; j < S.size(); j++) {
`bool` is_strictly_increasing = true;
for(`int` k = i; k < j; k++) {
is_strictly_increasing &= (S[k] < S[k+1]);
}
if(is_strictly_increasing) {
answer[j] = max(answer[j], j - i + 1);
}
}
}
return answer;
}

We cannot check each substring of string $$$\mathbf{S}$$$ for this test set due to the large constraints. We already know that, for a string $$$\mathbf{S}$$$ to be strictly increasing, $$$\mathbf{S_i} \lt \mathbf{S_{i+1}}$$$ for $$$1 \le i \lt \mathbf{N}$$$. Consider that we have already calculated the length of the longest strictly increasing substring that ends at position $$$i$$$. Let this length be $$$MaxLen(i)$$$. Now we need to compute the answer for position $$$i+1$$$. There is no need to consider all substrings ending at position $$$i+1$$$. We can simply check if $$$\mathbf{S_i} \lt \mathbf{S_{i+1}}$$$. If this condition is satisfied, we can simply append S(i+1) to the longest increasing substring ending at i and it would still be increasing and update $$$MaxLen(i+1) = MaxLen(i) + 1$$$. Otherwise, $$$MaxLen(i) = 1$$$. This way, we can calculate the length of the longest strictly increasing substring that ends at position $$$i$$$ in constant time. Hence, the overall time complexity of the solution is $$$O(\mathbf{N})$$$.

Consider the following example with string $$$bbcda$$$. For index $$$1$$$, $$$MaxLen(1) = 1$$$. For index $$$2$$$, we can see that index $$$1$$$ and index $$$2$$$ have equal values and thus do not satisfy the constraint $$$\mathbf{S_i} \lt \mathbf{S_{i+1}}$$$. In this case, $$$MaxLen(2) = 1$$$. For index $$$3$$$, $$$\mathbf{S_2} \lt \mathbf{S_3}$$$, hence we can extend the longest strictly increasing substring ending at index $$$\mathbf{2}$$$. In this case, $$$MaxLen(3) = 2$$$. For index $$$4$$$, $$$\mathbf{S_3} \lt \mathbf{S_4}$$$, hence we can extend the longest strictly increasing substring ending at index $$$\mathbf{3}$$$. In this case, $$$MaxLen(4) = 3$$$. For index $$$4$$$, $$$\mathbf{S_4} \gt \mathbf{S_5}$$$ which violates the condition for strictly increasing substring. In this case, $$$MaxLen(5) = 1$$$.

```
vector<
````int`> longestStrictlyIncreasingSubstring(string S) {
vector<`int`> answer(S.size(), 0);
answer[0] = 1;
for(`int` i = 1; i < S.size(); i++) {
if(S[i - 1] < S[i]) {
answer[i] = answer[i - 1] + 1;
}
else {
answer[i] = 1;
}
}
return answer;
}

Test Data

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

For any test case, if $$$\mathbf{N} = 2$$$, we can return $$$2$$$ as the answer immediately, as any two numbers are trivially an arithmetic progression by themselves.
For $$$\mathbf{N} \ge 3$$$, we can attempt a strategy that tries to improve it by considering every element of $$$\mathbf{A}$$$ as a possible starting point.
For instance, let us try to start a longest progression beginning at $$$\mathbf{A_0}$$$. Let us call the first difference we encounter, $$$\mathbf{A_1} - \mathbf{A_0}$$$, $$$d$$$. $$$d$$$ could be the common difference of a longest progression
that starts from $$$\mathbf{A_0}$$$, or it could not be. We attempt both possibilities:

- If it is, we just need to continue trying to extend our possible progression with $$$\mathbf{A_2}$$$, $$$\mathbf{A_3}$$$ and so on, checking that $$$\mathbf{A_2} - \mathbf{A_1} = d$$$, $$$\mathbf{A_3} - \mathbf{A_2} = d$$$, etc. Because we can change at most one number, the first time we find some $$$k$$$ for which $$$\mathbf{A_k}- \mathbf{A_{k-1}} \ne d$$$, we fix $$$\mathbf{A_k}$$$ so that this expression does equal to $$$d$$$. We continue along the array afterwards until we reach the end or we find a second instance of $$$k$$$ where $$$\mathbf{A_k} - \mathbf{A_{k-1}} \ne d$$$; at that point, we cannot go any further.
- If it is not, the only possibility for a progression with length $$$>= 3$$$ starting from $$$\mathbf{A_0}$$$ is if the common difference is $$$(\mathbf{A_2} - \mathbf{A_0}) / 2$$$. In this case, we must set $$$\mathbf{A_1}$$$ such that $$$(\mathbf{A_1} - \mathbf{A_0}) = (\mathbf{A_2} - \mathbf{A_1})$$$. Hence, note that this is only possible if $$$\mathbf{A_2} - \mathbf{A_0}$$$ is an even number - if it is not, we can determine the longest progression starting at $$$\mathbf{A_0}$$$ under this scenario to simply be $$$2$$$ (as we cannot extend it past the first two values of the array). Once we have done so, our common difference is set, and we continue trying to extend our progression starting from $$$\mathbf{A_3}$$$, $$$\mathbf{A_4}$$$, and so on, stopping at the first $$$\mathbf{A_k}$$$ where $$$(\mathbf{A_1} - \mathbf{A_0}) \ne (\mathbf{A_k} - \mathbf{A_{k-1}})$$$. At that point, the length of the longest progression starting at $$$\mathbf{A_0}$$$ under this scenario will be $$$k$$$.

Both possibilities $$$1$$$ and $$$2$$$ take $$$O(\mathbf{N})$$$ for a given starting point. Because we will try sequentially all possible starting points from $$$\mathbf{A_0}, \mathbf{A_1}, \dots, \mathbf{A_{N-2}}$$$, finding the max value amongst all $$$\mathbf{N}-1$$$ possible starting points with $$$2$$$ possible scenarios each, our overall time complexity with this strategy will be $$$O(\mathbf{N}^{2})$$$.

Let's simplify the problem a little. The only thing that really matters in this situation is the common difference between two adjacent numbers, not the numbers themselves.
That is, the length of the longest progression of $$$[a, b, c, d, e, f]$$$ is always going to be the same as that of
$$$[a+k, b+k, c+k, d+k, e+k, f+k]$$$.
So, we can create an array $$$D$$$ where $$$D_i = \mathbf{A_{i+1}} - \mathbf{A_i}$$$. $$$D_0$$$ is hence $$$\mathbf{A_1} - \mathbf{A_0}$$$, and so on, until $$$D_{\mathbf{N}-2}$$$ which is $$$\mathbf{A_{N-1}} - \mathbf{A_{N-2}}$$$.
For instance, given $$$\mathbf{A} = [1, 3, 4, 7, 9, 11]$$$, we find that $$$D = [2, 1, 3, 2, 2]$$$.

Now, we can break $$$D$$$ into *chunks*. Each chunk is a contiguous portion of the array with identical values. For a given chunk, let us call this value its *common value*. For instance, for $$$D = [2, 1, 3, 2, 2]$$$, we can break this down as $$$[2], [1], [3], [2, 2]$$$, so $$$2$$$ is the common value of the first chunk, and so on.
Each chunk has a starting index within $$$D$$$. That index should be associated with the length and common value of that chunk, and this information stored for lookup.
Then, we iterate through the chunks in ascending starting index order. For each chunk beginning at index $$$i$$$, with length $$$k$$$, and having common value $$$d$$$, we greedily try to fix the element in $$$D$$$ right after the chunk, if it exists. Then, we also need a separate attempt to try fixing the element right before the chunk, if it exists. That means we will need to attempt merging for each chunk up to two times. The following analysis is for
what happens when we merge with the element *after* our current chunk, but the same applies for the corresponding situation when we merge backwards too.

The last element in our current chunk has index $$$(i+k-1)$$$. If we greedily use our ability to change a number by *adding* some amount to $$$D_{i+k}$$$ so it is equal to $$$d$$$, we must also reduce $$$D_{i+k+1}$$$ by the same amount. The opposite case applies. At this point:

- if $$$D_{i+k} + D_{i+k+1} \ne 2 \times d$$$, then we have only been able to merge our current chunk with the element right after. The length of our extended chunk is now $$$k + 1$$$.
- if $$$D_{i+k} + D_{i+k+1} = 2 \times d$$$, but $$$D_{i+k+2} \ne d$$$, then changing $$$D_{i+k}$$$ has allowed us to also merge with $$$D_{i+k+1}$$$. The length of our extended chunk is now $$$k + 2$$$.
- if $$$D_{i+k} + D_{i+k+1} = 2 \times d$$$, and $$$D_{i+k+2} = d$$$, then we have been able to merge even further with a chunk that starts $$$3$$$ elements after our current one ends. The length of the whole merge becomes $$$k + 2 + $$$ the length of the next chunk with common value $$$d$$$.

Our overall solution to the problem is then just the max of all the possible chunks made by considering each chunk in turn, and trying to merge it backwards and forwards. (As a result, if the test case in question falls into the third scenario listed above, the "longest progression" will actually be discovered twice, but this doesn't change its correctness.)

In summary, we run through the initial array once to create $$$D$$$, and then run through $$$D$$$ to create map(s) of chunks tagged with the appropriate information, and then run through $$$D$$$ again with our map of chunks to finally get our result. Assuming we have access to constant-time lookup for the lengths and common values of chunks, the overall time complexity is $$$O(\mathbf{N})$$$.

Test Data

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

Say $$$P(n)$$$ denotes the number of primes up to $$$n$$$, then the number of possible products of consecutive primes will be $$$P(n) - 1$$$. For this test set, we can find all the primes up to $$$n = 2021$$$ and generate the list of products of consecutive primes. Each query can then be answered by searching for the largest product which is still smaller than or equal to the given query.

*Complexity analysis:*

- To generate primes, we can test all $$$i$$$ up to $$$n$$$ for primality by checking if any integer from $$$2$$$ to $$$i - 1$$$ divides $$$i$$$. This takes $$$\sum_{i=0}^{n-2}i = O(n^2)$$$
- Generating the list of products of consecutive primes from the prime list takes $$$O(n)$$$ (a tighter bound will be $$$O(P(n))$$$ but we do not require it for this case)
- To answer all the queries, the complexity is $$$O(T \times n)$$$

So, the total complexity is $$$O(n^2) + O(T \times n)$$$ which is well under the required time limit for $$$n = 2021$$$.

We do not need to generate all the primes up to $$$n$$$, but only until we find a prime which is greater than $$$\sqrt{n}$$$. The product of consecutive primes larger than $$$\sqrt{n}$$$ will be greater than $$$n$$$. For this test set, $$$n$$$ can be up to $$$10^9$$$, so we can generate primes up to $$$10^5$$$ (rounding off $$$10^{4.5}$$$ to cover the one up case as well) using Sieve of Eratosthenes.

*Complexity analysis:* $$$O( \sqrt{n} \times \log( \log( \sqrt{n} ) ) )$$$ (for
sieve) + $$$O( T \times P(\sqrt{n}) )$$$ (for queries) which is well under the
required time limit for $$$n = 10^9$$$.

Our previous strategy of generating primes up to $$$\sqrt{n}$$$ will not work in this case as $$$\sqrt{n}$$$ can be as large as $$$10^{9}$$$.

For any input $$$n$$$, there can be only two scenarios:

- The solution is the product of the largest prime smaller than or equal to $$$\sqrt{n}$$$ and the smallest prime greater than $$$\sqrt{n}$$$. Product of consecutive primes larger than that will be larger than $$$n$$$.
- The solution is the product of two largest primes smaller than or equal to $$$\sqrt{n}$$$. This will be less than $$$n$$$ and any product of consecutive primes less than that will be even smaller.

So, we need primes only in the vicinity of $$$\sqrt{n}$$$, specifically in the worst case, $$$2$$$ primes smaller than or equal to $$$\sqrt{n}$$$ and one prime larger than $$$\sqrt{n}$$$.

Now, how far out can the closest prime be from any given $$$\sqrt{n}$$$? This series of numbers is known as maximal prime gaps and for $$$\sqrt{n} = 10^{9}$$$ (for maximum possible $$$n = 10^{18}$$$), this number is $$$282$$$ (called $$$max\_gap$$$ from now on). So, we can iterate backwards from $$$\sqrt{n}$$$ until we find $$$2$$$ primes and then iterate ahead from $$$\sqrt{n}$$$ for $$$1$$$ more prime. In the worst case we would need to check integers in range $$$[\sqrt{n} - max\_gap \times 2, \sqrt{n} + max\_gap]$$$.

*Complexity analysis:* $$$O( \sqrt[4]{n} \times 3 \times max\_gap \times T
)$$$

(primality check over $$$3 \times max\_gap$$$ possible integers for
$$$T$$$ test cases)

*Note:* The above complexity is not a tight bound. It's hard to hit the
worst case scenario and even then most of the primality checks will terminate
earlier (using just the first $$$7$$$ primes, we can rule out $$$662$$$ integers
in any $$$3 \times 282$$$ range). A better
primality test can be
used to further drive the complexity down.
Segmented sieve can also be used to have deterministic complexity -
$$$O( ( \sqrt[4]{n} + 3 \times max\_gap \times T) \times \log( \log( \sqrt[4]{n}
)))$$$.

Test Data

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

Let us root the tree at the capital city $$$1$$$. For the small test set, we can answer each query by simply iterating the path from the given city $$$\mathbf{C_j}$$$ up to the capital city. We start out with the answer $$$ans = 0$$$, and whenever we encounter a road on the path with $$$\mathbf{L_i} \leq \mathbf{W_j}$$$, we update the answer to $$$ans = \gcd(ans, \mathbf{A_i}$$$).

The time complexity of the Greatest Common Divisor (GCD) operation $$$\gcd(a, b)$$$ is $$$O(\log(\min(a, b)))$$$ or $$$O(\log(MaxA))$$$ in our case, where $$$MaxA$$$ is the largest toll among all roads. A short proof of GCD time complexity is provided here, and it can be generalized to show that the amortized time complexity of a sequence of $$$K$$$ GCD operations, where the result of a previous operation is fed into the next one, is $$$O(K + \log(MaxA))$$$ as opposed to $$$O(K \times \log(MaxA))$$$. Since a path in the tree can have up to $$$\mathbf{N}$$$ cities, the overall time complexity of the algorithm for all $$$\mathbf{Q}$$$ days is therefore $$$O(\mathbf{Q} \times (\mathbf{N} + \log(MaxA)))$$$.

Since all queries are known in advance, we do not have to answer them in the given order, so let's group the queries by city $$$\mathbf{C_j}$$$.

Let's look at how we can answer all queries for a particular city $$$C$$$ efficiently. First, we need to build a list of roads on the path from city $$$C$$$ to the capital city $$$1$$$ and sort them by the load-limits $$$\mathbf{L_i}$$$ in an increasing order. Let's also sort the queries for city $$$C$$$ by weight $$$\mathbf{W_j}$$$ in a non-decreasing order. Now we can answer the queries by iterating these two lists in parallel and calculating GCD of all roads with load-limit up to and including the weight $$$\mathbf{W_j}$$$ of the current query.

The time complexity of this approach is $$$O(\mathbf{N}^2 \log(\mathbf{N}) + \mathbf{N} \log(MaxA) + \mathbf{Q} \log(\mathbf{Q}))$$$ as we need to sort the list of roads from each city to the capital city $$$1$$$, perform a series of GCD operations for each of these $$$\mathbf{N}$$$ paths, and also have the queries sorted by loads.

Rather than building paths to the capital for each city independently, we can perform a Depth-first search (DFS) of the tree starting at the capital city $$$1$$$ and answer all queries of a city $$$C$$$ as we visit the city for the first time. That way, the cities and roads on the path from $$$C$$$ to $$$1$$$ are conveniently stored in the DFS stack. All we need is an efficient data structure that would store the toll $$$\mathbf{A_i}$$$ of precisely these roads and support GCD queries of tolls in the load-limit range $$$[1, \mathbf{W_j}]$$$.

That data structure happens to be a segment tree $$$ST$$$ with load-limits $$$\mathbf{L_i}$$$ as keys (recall that all load-limits are unique), the tolls $$$\mathbf{A_i}$$$ as values, and GCD as the merge operation. Initially, the segment tree $$$ST$$$ is empty, namely, the values of all its nodes are $$$0$$$. Whenever we traverse the $$$i$$$-th road, we perform a point update operation $$$ST.update(\mathbf{L_i}, \mathbf{A_i})$$$, and, when we backtrack along this road in the DFS traveral, we cancel the value $$$\mathbf{A_i}$$$ by calling $$$ST.update(\mathbf{L_i}, 0)$$$. By doing so, we ensure that at the time of answering queries for a particular city, the segment tree $$$ST$$$ contains the tolls of precisely the roads on the path to the capital city $$$1$$$, and the answer to a query is $$$ST.query(1, \mathbf{W_j})$$$.

Let $$$MaxQ$$$ be the maximum load-limit among all roads. Each update or query of the segment tree involves $$$O(\log(MaxQ))$$$ GCD operations so the amortized time complexity of a single update or query operation is $$$O(\log(MaxA) + \log(MaxQ))$$$. Since we have two update operations per road and one query operation per each day, the overall time complexity of the algorithm is $$$O((\mathbf{N} + \mathbf{Q}) \times (\log(MaxA) + \log(MaxQ)))$$$.

Test Data

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