1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Hamon Odyssey
Contest: Codeforces Round 882 (Div. 2)
Difficulty rating: 1000
Tags: bitmasks, greedy, two pointers

Jonathan is fighting against DIO's Vampire minions. There are $$$n$$$ of them with strengths $$$a_1, a_2, \dots, a_n$$$. $$$\def\and {{\,\texttt{&}\,}}$$$

Denote $$$(l, r)$$$ as the group consisting of the vampires with indices from $$$l$$$ to $$$r$$$. Jonathan realizes that the strength of any such group is in its weakest link, that is, the bitwise AND. More formally, the strength level of the group $$$(l, r)$$$ is defined as $$$$$$f(l,r) = a_l \and a_{l+1} \and a_{l+2} \and \ldots \and a_r.$$$$$$ Here, $$$\and$$$ denotes the bitwise AND operation.

Because Jonathan would like to defeat the vampire minions fast, he will divide the vampires into contiguous groups, such that each vampire is in exactly one group, and the sum of strengths of the groups is minimized. Among all ways to divide the vampires, he would like to find the way with the maximum number of groups.

Given the strengths of each of the $$$n$$$ vampires, find the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.

Input format:
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of vampires.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the individual strength of each vampire.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the optimal way is to take all the $$$n$$$ vampires as a group. So, $$$f(1,3) = 1 \and 2 \and 3 = 0$$$.

In the second test case, the optimal way is to make $$$2$$$ groups, $$$(2,3,1)$$$ and $$$(5,2)$$$. So, $$$f(1,3) + f(4,5) = (2 \and 3 \and 1) + (5 \and 2) = 0 + 0 = 0$$$.

Example input:
3
3
1 2 3
5
2 3 1 5 2
4
5 7 12 6

Example output:
1
2
1

Editorial:
There are two cases in this problem. First, if $$$f(1,n) > 0$$$, then maximum number of groups becomes $$$1$$$. This is because there are some bits set in all the elements. Now, if we divide the array in more than one group, then these bits are taken more than once which will not give smallest AND. Second case is when $$$f(1,n) = 0$$$. This means the smallest AND is $$$0$$$. Now, we need to greedily divide the array into subarrays such that the AND of each subarray should be $$$0$$$. We keep taking elements in the subarray until the AND becomes $$$0$$$. When AND becomes $$$0$$$, we take remaining elements in the next subarray. If the last subarray has AND more than $$$0$$$, then we need to merge that subarray with the previous subarray.
Time complexity - $$$O(n)$$$.
Malek Dance Club
Contest: Codeforces Round 189 (Div. 1)
Difficulty rating: 1600
Tags: combinatorics, math

As a tradition, every year before IOI all the members of Natalia Fan Club are invited to Malek Dance Club to have a fun night together. Malek Dance Club has 2n members and coincidentally Natalia Fan Club also has 2n members. Each member of MDC is assigned a unique id i from 0 to 2n - 1. The same holds for each member of NFC.

One of the parts of this tradition is one by one dance, where each member of MDC dances with a member of NFC. A dance pair is a pair of numbers (a, b) such that member a from MDC dances with member b from NFC.

The complexity of a pairs' assignment is the number of pairs of dancing pairs (a, b) and (c, d) such that a < c and b > d.

You are given a binary number of length n named x. We know that member i from MDC dances with member $$i \oplus x$$ from NFC. Your task is to calculate the complexity of this assignment modulo 1000000007 (109 + 7).

Expression $$x \oplus y$$ denotes applying «XOR» to numbers x and y. This operation exists in all modern programming languages, for example, in C++ and Java it denotes as «^», in Pascal — «xor».

Input format:
The first line of input contains a binary number x of lenght n, (1 ≤ n ≤ 100).

This number may contain leading zeros.

Output format:
Print the complexity of the given dance assignent modulo 1000000007 (109 + 7).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
11

Example output:
6

Example input:
01

Example output:
2

Editorial:
Psychos in a Line
Contest: Codeforces Round 189 (Div. 1)
Difficulty rating: 1900
Tags: data structures, implementation

There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step.

You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.

Input format:
The first line of input contains integer n denoting the number of psychos, (1 ≤ n ≤ 105). In the second line there will be a list of n space separated distinct integers each in range 1 to n, inclusive — ids of the psychos in the line from left to right.

Output format:
Print the number of steps, so that the line remains the same afterward.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1]  →  [10 8 4]  →  [10]. So, there are two steps.

Example input:
10
10 9 7 8 6 5 3 4 2 1

Example output:
2

Example input:
6
1 2 3 4 5 6

Example output:
0

Editorial:
Kalila and Dimna in the Logging Industry
Contest: Codeforces Round 189 (Div. 1)
Difficulty rating: 2100
Tags: dp, geometry

Kalila and Dimna are two jackals living in a huge jungle. One day they decided to join a logging factory in order to make money.

The manager of logging factory wants them to go to the jungle and cut n trees with heights a1, a2, ..., an. They bought a chain saw from a shop. Each time they use the chain saw on the tree number i, they can decrease the height of this tree by one unit. Each time that Kalila and Dimna use the chain saw, they need to recharge it. Cost of charging depends on the id of the trees which have been cut completely (a tree is cut completely if its height equal to 0). If the maximum id of a tree which has been cut completely is i (the tree that have height ai in the beginning), then the cost of charging the chain saw would be bi. If no tree is cut completely, Kalila and Dimna cannot charge the chain saw. The chainsaw is charged in the beginning. We know that for each i < j, ai < aj and bi > bj and also bn = 0 and a1 = 1. Kalila and Dimna want to cut all the trees completely, with minimum cost.

They want you to help them! Will you?

Input format:
The first line of input contains an integer n (1 ≤ n ≤ 105). The second line of input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109). The third line of input contains n integers b1, b2, ..., bn (0 ≤ bi ≤ 109).

It's guaranteed that a1 = 1, bn = 0, a1 < a2 < ... < an and b1 > b2 > ... > bn.

Output format:
The only line of output must contain the minimum cost of cutting all the trees completely.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5
1 2 3 4 5
5 4 3 2 0

Example output:
25

Example input:
6
1 2 3 10 20 30
6 5 4 3 2 0

Example output:
138

Editorial:
Have You Ever Heard About the Word?
Contest: Codeforces Round 189 (Div. 1)
Difficulty rating: 2800
Tags: greedy, hashing, string suffix structures, strings

A substring of a string is a contiguous subsequence of that string. So, string bca is substring of string abcabc, but string cc is not.

A repeating block is a string formed by concatenating some string with itself. So, string abcabc is a repeating block, but strings abcabd, ababab are not.

You've got a sequence of Latin characters (string). At each step you find the shortest substring that is a repeating block, if there exists more than one you must choose the leftmost. As the substring is of form XX (X — some string) you replace this substring with X, in other words you delete one of the X substrings in the substring. You repeat this process until there remains no repeating block in the string.

How would the final string looks like? Look at the sample explanation to understand the statement more precise.

Input format:
In the first line of input you're given a string of small Latin characters with length between 1 to 50000, inclusive.

Output format:
Print the final string after applying changes.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
At the first sample the string transforms as follows: abccabc  →  abcabc  →  abc.

At the second sample the string transforms as follows: aaaabaaab  →  aaabaaab  →  aabaaab  →  abaaab  →  abaab  →  abab  →  ab.

Example input:
abccabc

Example output:
abc

Example input:
aaaabaaab

Example output:
ab

Editorial:
Ping-Pong
Contest: Codeforces Round 189 (Div. 1)
Difficulty rating: 3000
Tags: data structures

In this problem at each moment you have a set of intervals. You can move from interval (a, b) from our set to interval (c, d) from our set if and only if c < a < d or c < b < d. Also there is a path from interval I1 from our set to interval I2 from our set if there is a sequence of successive moves starting from I1 so that we can reach I2.

Your program should handle the queries of the following two types:

1. "1 x y" (x < y) — add the new interval (x, y) to the set of intervals. The length of the new interval is guaranteed to be strictly greater than all the previous intervals.
2. "2 a b" (a ≠ b) — answer the question: is there a path from a-th (one-based) added interval to b-th (one-based) added interval?

Answer all the queries. Note, that initially you have an empty set of intervals.

Input format:
The first line of the input contains integer n denoting the number of queries, (1 ≤ n ≤ 105). Each of the following lines contains a query as described above. All numbers in the input are integers and don't exceed 109 by their absolute value.

It's guaranteed that all queries are correct.

Output format:
For each query of the second type print "YES" or "NO" on a separate line depending on the answer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5
1 1 5
1 5 11
2 1 2
1 2 9
2 1 2

Example output:
NO
YES

Editorial:
Jeff and Digits
Contest: Codeforces Round 204 (Div. 2)
Difficulty rating: 1000
Tags: brute force, implementation, math

Jeff's got n cards, each card contains either digit 0, or digit 5. Jeff can choose several cards and put them in a line so that he gets some number. What is the largest possible number divisible by 90 Jeff can make from the cards he's got?

Jeff must make the number without leading zero. At that, we assume that number 0 doesn't contain any leading zeroes. Jeff doesn't have to use all the cards.

Input format:
The first line contains integer n (1 ≤ n ≤ 103). The next line contains n integers a1, a2, ..., an (ai = 0 or ai = 5). Number ai represents the digit that is written on the i-th card.

Output format:
In a single line print the answer to the problem — the maximum number, divisible by 90. If you can't make any divisible by 90 number from the cards, print -1.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test you can make only one number that is a multiple of 90 — 0.

In the second test you can make number 5555555550, it is a multiple of 90.

Example input:
4
5 0 5 0

Example output:
0

Example input:
11
5 5 5 5 5 5 5 5 0 5 5

Example output:
5555555550

Editorial:
Jeff and Periods
Contest: Codeforces Round 204 (Div. 2)
Difficulty rating: 1300
Tags: implementation, sortings

One day Jeff got hold of an integer sequence a1, a2, ..., an of length n. The boy immediately decided to analyze the sequence. For that, he needs to find all values of x, for which these conditions hold:

- x occurs in sequence a.
- Consider all positions of numbers x in the sequence a (such i, that ai = x). These numbers, sorted in the increasing order, must form an arithmetic progression.

Help Jeff, find all x that meet the problem conditions.

Input format:
The first line contains integer n (1 ≤ n ≤ 105). The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 105). The numbers are separated by spaces.

Output format:
In the first line print integer t — the number of valid x. On each of the next t lines print two integers x and px, where x is current suitable value, px is the common difference between numbers in the progression (if x occurs exactly once in the sequence, px must equal 0). Print the pairs in the order of increasing x.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test 2 occurs exactly once in the sequence, ergo p2 = 0.

Example input:
1
2

Example output:
1
2 0

Example input:
8
1 2 1 3 1 2 1 5

Example output:
4
1 2
2 4
3 0
5 0

Editorial:
Maximize?
Contest: Codeforces Round 943 (Div. 3)
Difficulty rating: 800
Tags: brute force, math, number theory

You are given an integer $$$x$$$. Your task is to find any integer $$$y$$$ $$$(1\le y<x)$$$ such that $$$\gcd(x,y)+y$$$ is maximum possible.

Note that if there is more than one $$$y$$$ which satisfies the statement, you are allowed to find any.

$$$\gcd(a,b)$$$ is the Greatest Common Divisor of $$$a$$$ and $$$b$$$. For example, $$$\gcd(6,4)=2$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each of the following $$$t$$$ lines contains a single integer $$$x$$$ ($$$2 \le x \le 1000$$$).

Output format:
For each test case, output any $$$y$$$ ($$$1 \le y < x$$$), which satisfies the statement.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
7
10
7
21
100
2
1000
6

Example output:
5
6
18
98
1
750
3

Editorial:
The core idea is to find the upper bound of $$$\gcd(x,y)+y$$$.
Let us look closer at the formula $$$\gcd(x,y)+y$$$. It is a well-known fact that $$$\gcd(a,b)=\gcd(a-b,b)$$$ for $$$a\geq b$$$. Applying it to our formula, we get $$$\gcd(x-y,y)+y$$$.
Using the fact that $$$\gcd(x-y,y)\le x-y$$$, we get $$$\gcd(x-y,y)+y\le x-y+y=x$$$. Hence, $$$\gcd(x,y)+y\le x$$$ for $$$1\le y<x$$$.
For $$$y=x-1$$$, we have $$$\gcd(x,x-1)+x-1=1+x-1=x$$$, which is the maximal possible value.
Note that the constraints allow finding the optimal $$$y$$$ in $$$O(x)$$$, while the above solution works in $$$O(1)$$$.
Prefiquence
Contest: Codeforces Round 943 (Div. 3)
Difficulty rating: 800
Tags: greedy, two pointers

You are given two binary strings $$$a$$$ and $$$b$$$. A binary string is a string consisting of the characters '0' and '1'.

Your task is to determine the maximum possible number $$$k$$$ such that a prefix of string $$$a$$$ of length $$$k$$$ is a subsequence of string $$$b$$$.

A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements.

Input format:
The first line consists of a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m \le 2 \cdot 10^5$$$) — the length of string $$$a$$$ and the length of string $$$b$$$, respectively.

The second line of each test case contains a binary string $$$a$$$ of length $$$n$$$.

The third line of each test case contains a binary string $$$b$$$ of length $$$m$$$.

It is guaranteed that the sum of values $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. Similarly, the sum of values $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single number — the maximum $$$k$$$, such that the first $$$k$$$ characters of $$$a$$$ form a subsequence of $$$b$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the string '$$$10$$$' is a subsequence of '$$$1\color{red}11\color{red}0$$$' but the string '$$$100$$$' is not. So the answer is $$$2$$$.

In the fifth example, $$$a$$$='$$$100$$$', $$$b$$$='$$$1\color{red}{10}1\color{red}0$$$', whole string $$$a$$$ is a subsequence of string $$$b$$$. So the answer is $$$3$$$.

In the sixth example, string $$$b$$$ does not contain '$$$1$$$' so the answer is $$$0$$$.

Example input:
6
5 4
10011
1110
3 3
100
110
1 3
1
111
4 4
1011
1111
3 5
100
11010
3 1
100
0

Example output:
2
2
1
1
3
0

Editorial:
We will be solving this task using dynamic programming.
Let us define $$$dp_i$$$ as the maximal prefix of $$$a$$$ that is contained in $$$b_1,\dots,b_i$$$ as a subsequence.
Then the transitions are as follows:
• if $$$b_i$$$ is equal to $$$a_{dp_{i-1}+1}$$$ then $$$dp_i = dp_{i-1} + 1$$$.
• otherwise $$$dp_i=dp_{i-1}$$$.
The answer is $$$dp_{m}$$$.
Assembly via Remainders
Contest: Codeforces Round 943 (Div. 3)
Difficulty rating: 1000
Tags: constructive algorithms, number theory

You are given an array $$$x_2,x_3,\dots,x_n$$$. Your task is to find any array $$$a_1,\dots,a_n$$$, where:

- $$$1\le a_i\le 10^9$$$ for all $$$1\le i\le n$$$.
- $$$x_i=a_i \bmod a_{i-1}$$$ for all $$$2\le i\le n$$$.

Here $$$c\bmod d$$$ denotes the remainder of the division of the integer $$$c$$$ by the integer $$$d$$$. For example $$$5 \bmod 2 = 1$$$, $$$72 \bmod 3 = 0$$$, $$$143 \bmod 14 = 3$$$.

Note that if there is more than one $$$a$$$ which satisfies the statement, you are allowed to find any.

Input format:
The first line contains a single integer $$$t$$$ $$$(1\le t\le 10^4)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(2\le n\le 500)$$$ — the number of elements in $$$a$$$.

The second line of each test case contains $$$n-1$$$ integers $$$x_2,\dots,x_n$$$ $$$(1\le x_i\le 500)$$$ — the elements of $$$x$$$.

It is guaranteed that the sum of values $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case output any $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) which satisfies the statement.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case $$$a=[3,5,4,9]$$$ satisfies the conditions, because:

- $$$a_2\bmod a_1=5\bmod 3=2=x_2$$$;
- $$$a_3\bmod a_2=4\bmod 5=4=x_3$$$;
- $$$a_4\bmod a_3=9\bmod 4=1=x_4$$$;

Example input:
5
4
2 4 1
3
1 1
6
4 2 5 1 2
2
500
3
1 5

Example output:
3 5 4 9
2 5 11
5 14 16 5 11 24
501 500
2 7 5

Editorial:
Notice that $$$((a+b) \bmod a)=b$$$ for $$$0\le b< a$$$. So we may try to generate a sequence with $$$b=x_i$$$.
Let us take $$$a_1=1000$$$, because $$$1000$$$ is larger than any of $$$x_i$$$. Then, we can take $$$a_i$$$ as $$$a_{i-1}+x_i$$$, since $$$((a_{i-1}+x_i)\bmod a_{i-1})=x_i$$$ will be hold.
The maximal value of $$$a$$$ will be at most $$$1000+500n$$$ what is smaller than $$$10^9$$$.
Cells Arrangement
Contest: Codeforces Round 943 (Div. 3)
Difficulty rating: 1600
Tags: constructive algorithms

You are given an integer $$$n$$$. You choose $$$n$$$ cells $$$(x_1,y_1), (x_2,y_2),\dots,(x_n,y_n)$$$ in the grid $$$n\times n$$$ where $$$1\le x_i\le n$$$ and $$$1\le y_i\le n$$$.

Let $$$\mathcal{H}$$$ be the set of distinct Manhattan distances between any pair of cells. Your task is to maximize the size of $$$\mathcal{H}$$$. Examples of sets and their construction are given in the notes.

If there exists more than one solution, you are allowed to output any.

Manhattan distance between cells $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ equals $$$|x_1-x_2|+|y_1-y_2|$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1\le t\le 50$$$) — the number of test cases.

Each of the following $$$t$$$ lines contains a single integer $$$n$$$ ($$$2\le n\le 10^3$$$).

Output format:
For each test case, output $$$n$$$ points which maximize the size of $$$\mathcal{H}$$$. It is not necessary to output an empty line at the end of the answer for each test case.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase we have $$$n=2$$$. One of the possible arrangements is:

The arrangement with cells located in $$$(1,1)$$$ and $$$(1,2)$$$.

In the second testcase we have $$$n=3$$$. The optimal arrangement is:

The arrangement with cells located in $$$(2,1)$$$, $$$(2,3)$$$ and $$$(3,1)$$$.

$$$\mathcal{H}$$$=$$$\{|2-2|+|1-1|,|2-2|+|3-3|,|3-3|+|1-1|,|2-2|+|1-3|,|2-3|+|1-1|,|2-3|+|3-1|\}$$$=$$$\{0,0,0,2,1,3\}$$$=$$$\{0,1,2,3\}$$$.

For $$$n=4$$$ a possible arrangement is:

For $$$n=5$$$ a possible arrangement is:

For $$$n=6$$$ a possible arrangement is:

Example input:
5
2
3
4
5
6

Example output:
1 1
1 2

2 1
2 3
3 1

1 1
1 3
4 3
4 4

1 1
1 3
1 4
2 1
5 5

1 4
1 5
1 6
5 2
5 5
6 1

Editorial:
Let us find an interesting pattern for $$$n\geq 4$$$.
spoiler: n=4;
spoiler: n=5;
Do you see it? We put $$$n-2$$$ cells on the main diagonal. Then put two cells at $$$(n-1,n)$$$ and $$$(n,n)$$$.
But why does it work? Interesting fact, that in such way we generate all possible Manhattan distances. Odd distances are generated between cells from the main diagonal and $$$(n-1,n)$$$. Even distances are generated between cells from the main diagonal and $$$(n,n)$$$.
Division + LCP (hard version)
Contest: Codeforces Round 943 (Div. 3)
Difficulty rating: 2200
Tags: binary search, brute force, data structures, dp, hashing, math, string suffix structures, strings

This is the hard version of the problem. In this version $$$l\le r$$$.

You are given a string $$$s$$$. For a fixed $$$k$$$, consider a division of $$$s$$$ into exactly $$$k$$$ continuous substrings $$$w_1,\dots,w_k$$$. Let $$$f_k$$$ be the maximal possible $$$LCP(w_1,\dots,w_k)$$$ among all divisions.

$$$LCP(w_1,\dots,w_m)$$$ is the length of the Longest Common Prefix of the strings $$$w_1,\dots,w_m$$$.

For example, if $$$s=abababcab$$$ and $$$k=4$$$, a possible division is $$$\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}$$$. The $$$LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})$$$ is $$$2$$$, since $$$ab$$$ is the Longest Common Prefix of those four strings. Note that each substring consists of a continuous segment of characters and each character belongs to exactly one substring.

Your task is to find $$$f_l,f_{l+1},\dots,f_r$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n \le 2 \cdot 10^5$$$) — the length of the string and the given range.

The second line of each test case contains string $$$s$$$ of length $$$n$$$, all characters are lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output $$$r-l+1$$$ values: $$$f_l,\dots,f_r$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
7
3 1 3
aba
3 2 3
aaa
7 1 5
abacaba
9 1 6
abababcab
10 1 10
aaaaaaawac
9 1 9
abafababa
7 2 7
vvzvvvv

Example output:
3 1 0 
1 1 
7 3 1 1 0 
9 2 2 2 0 0 
10 3 2 1 1 1 1 1 0 0 
9 3 2 1 1 0 0 0 0 
2 2 1 1 1 0

Editorial:
In general, in this version we must answer for each $$$k\in\{1,2,\dots,n\}$$$. We will use a similar idea as in the easy version considering two cases:
• $$$k\le \sqrt{n}$$$. We may calculate these values as in the easy version in $$$O(n\sqrt{n}\log n)$$$.
• $$$k> \sqrt{n}$$$. As we divide the string into $$$k$$$ segments and the LCP is $$$\ell$$$, then $$$k\cdot \ell\le n$$$. We get, that $$$\ell\le \sqrt{n}$$$. We may find the maximal possible $$$k$$$ for a fixed $$$\ell$$$ as our answer. It works in $$$O(n\sqrt{n})$$$.
There are other approaches to solving this problem, but the authors believe this solution is the simplest one.