The annual "Phantom Pavilion Summer Wine Tasting Conference" features two events: tasting and a fun challenge. The tasting event awards the title of "Chief Taster," and the challenge event awards "Chief Hunter." Many wine tasters participate.

At the conference dinner, bartender Rainbow prepares n glasses of cocktails arranged in a line. Each glass i (1 ≤ i ≤ n) has a label si, which is one of the 26 lowercase English letters. Let str(l, r) denote the string formed by concatenating the labels from glass l to glass r. Two glasses p and q are considered "r-similar" if str(p, p0) = str(q, q0), where 1 ≤ p ≤ p0 ≤ n, 1 ≤ q ≤ q0 ≤ n, p ≠ q, and p0 - p + 1 = q0 - q + 1 = r. Consequently, any two glasses that are "r-similar" (where r > 1) are also "1-similar," "2-similar," ..., "(r - 1)-similar." Importantly, for any 1 ≤ p, q ≤ n with p ≠ q, glasses p and q are always "0-similar."

During the tasting session, taster Freda easily assessed the deliciousness of each cocktail. The deliciousness of glass i (1 ≤ i ≤ n) is given by ai. Rainbow then announced the challenge question: cocktails have a unique property such that mixing glass p and glass q yields a cocktail with deliciousness ap × aq. For each r from 0 to n-1, participants must count the number of pairs of glasses that are "r-similar" and find the maximum deliciousness achievable by mixing two "r-similar" glasses.

Input Format

The first line contains a single positive integer n, the number of cocktails.

The second line contains a string S of length n, where the i-th character represents the label of the i-th cocktail.

The third line contains n integers, separated by single spaces, where the i-th integer is the deliciousness ai of the i-th cocktail.

Output Format

Output n lines. The i-th line should contain two integers separated by a single space: the count of pairs of "(i-1)-similar" glasses, and the maximum deliciousness achievable by mixing two "(i-1)-similar" glasses. If no such pairs exist, both numbers should be 0.

Sample Input 1

10
ponoiiipoi
2 1 4 7 4 8 3 6 4 7
   

Sample Output 1

45 56
10 56
3 32
0 0
0 0
0 0
0 0
0 0
0 0
0 0
   

Sample Input 2

12
abaabaabaaba
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12
   

Sample Output 2

66 120
34 120
15 55
12 40
9 27
7 16
5 7
3 -4
2 -4
1 -4
0 0
0 0
   

Hint

Sample Explanation 1

Pairs are represented as (p, q) for glasses p and q.

• 0-similar: All 45 pairs are 0-similar. Maximum deliciousness is 8 × 7 = 56.
• 1-similar: (1,8), (2,4), (2,9), (4,9), (5,6), (5,7), (5,10), (6,7), (6,10), (7,10). Maximum deliciousness is 8 × 7 = 56.
• 2-similar: (1,8), (4,9), (5,6). Maximum deliciousness is 4 × 8 = 32.
• No 3, 4, ..., 9-similar pairs exist, so output 0 for all.

Time Limit: 1s, Memory Limit: 512MB

Problem Summary

• Given a string s of length n.
• For r ∈ [0, n):
  • Count the number of pairs (i, j) such that 1 ≤ i < j ≤ n and the Longest Common Prefix (LCP) of suffix starting at i and suffix starting at j is at least r.
  • Find the maximum value of ai × aj among pairs satisfying LCP(i, j) ≥ r.

Approach

Step 1: Suffix Array Foundation

The problem involves the Longest Common Prefix (LCP) of substrings, which strongly suggests the use of a Suffix Array. The LCP between two suffixes starting at indices i and j is determined by the minimum value in the height array between their respective positions in the sorted suffix array. Specifically, if the sorted suffixes are SAp and SAq (assuming p < q), their LCP is min{heightx | p < x ≤ q}.

The condition "r-similar" implies that the LCP of the corresponding suffixes must be at least r. Therefore, the problem transforms into finding pairs of suffixes (SAi, SAj) such that the minimum height value between their sorted positions (i.e., min {heightx | min(i, j) < x ≤ max(i, j)}) is greater than or equal to r.

Step 2: Transforming the Condition

Dealing with "greater than or equal to" conditions can be cumbersome. A common technique is to convert this into an "equal to" condition and then use suffix sums. The problem can be rephrased to find pairs where the minimum LCP value is exactly r, and then sum up the results for r' = r, r+1, ..., n-1.

The problem now becomes: for each r, count pairs of suffixes whose LCP is exactly r, and find the maximum product ai × aj for such pairs. We can then aggregate these results.

Step 3: Efficiently Handling Range Minimums

We need to find answers for ranges where the minimum height value is a specific value r. This type of problem, "find answers for intervals based on their minimum/maximum," is often solved using a Cartesian tree or a Disjoint Set Union (DSU) data structure. Given the need to merge adjacent segments and accumulate counts and maximums, DSU is a suitable choice here.

The strategy is to process the height values in decreasing order. When considering a height value h, it represents the minimum LCP for a contiguous block of suffixes in the sorted suffix array. We can use DSU to merge adjacent blocks that have an LCP of at least h.

Step 4: Merging and Updating

When merging two blocks (represented by DSU sets) with sizes size1 and size2 respectively, and the minimum height connecting them is len:

• Count: The number of new pairs formed by merging these two blocks is size1 \* size2. This contributes to the count for LCPs equal to len.
• Maximum Product: To find the maximum product, we need to consider the maximum and minimum deliciousness values within each block. The potential maximum products at the merge point are max1 \* max2, max1 \* min2, min1 \* max2, and min1 \* min2, where max1, min1 are the max/min deliciousness in the first block, and max2, min2 are for the second. The maximum of these, along with the maximum products already computed within each block, gives the new maximum product for the merged block.

After processing all height values from largest to smallest, we will have the counts and maximum products for LCPs that are exactly equal to a certain value. To get the results for LCPs at least r, we perform suffix sums on the counts and take the maximum for the products. Implementation Details

The solution involves constructing the Suffix Array and LCP array first. Then, a DSU structure is used to manage the merging process. The DSU should store the size of each set, the maximum deliciousness, the minimum deliciousness, and the maximum product found so far within the set. We iterate through the LCP array (specifically, the height values) in descending order, merging adjacent suffixes based on thier LCP values. For each merge operation at LCP value h, we update the total count of pairs with LCP exactly h and the maximum product for LCPs exactly h. Finally, we compute prefix sums (or suffix sums in this case, processing from largest LCP to smallest) for the counts and take maximums for the products to get the final answers for "at least r-similar" pairs.

Code Structure

The provided C++ code implements this logic:

• SuffixArray struct: Handles the construction of the suffix array (sa) and LCP array (height).
• Union struct: Implements the Disjoint Set Union data structure. It maintains p (parent), sz (size of set), mx (max deliciousness), mn (min deliciousness), and ans (max product within the set). The merge function updates these values and contributes to the global res1 (counts) and res2 (max products).
• Main function:
  • Initializes the DSU structure.
  • Constructs the suffix array and LCP array for the input string.
  • Sorts the indices of the suffix array based on the height array to process them in decreasing order of LCP.
  • Iterates through the sorted indices, merging adjacent suffixes in the suffix array using the u.merge function. The len parameter passed to merge is the height value.
  • Performs suffix sums on res1 and res2 to aggregate results for "at least r-similar" pairs.
  • Prints the final results.

Key Concepts and Tricks

• Suffix Array (SA): The LCP between two suffixes i and j is min {height\[x\]} where x ranges between their positions in the sorted suffix array.
• Disjoint Set Union (DSU): Useful for problems requiring the aggregation of information over intervals defined by minimum/maximum values. By processing height values from largest to smallest (or smallest to largest), we can merge adjacent segments and compute the required statistics (counts, maximums).