Phantom Pavilion Summer Tasting Challenge

The annual "Phantom Pavilion Summer Tasting Challenge" has kicked off. The contest consists of two parts: a tasting round and a fun challenge round. In the tasting round, the connoisseur Freda has evaluated every cocktail’s deliciousness, and in the challenge round, participants need to pick two cocktails that are r-similar and mix them together. When two cocktails are mixed, the resulting drink has a deliciousness equal to the product of the two individual deliciousness values. At the end of the contest, two awards are given: "Chief Taster" and "Chief Hunter".

At the dinner after the tasting round, the mixologist Rainbow prepared n cocktails, arranged in a row. The i-th cocktail (1 ≤ i ≤ n) is labeled with a lowercase letter s_i (one of the 26 lowercase letters). Let str(l, r) denote the string obtained by concatenating the labels from the l-th cocktail to the r-th cocktail (inclusive).

For any two different cocktails at positions p and q (1 ≤ p, q ≤ n, p ≠ q), if there exist indices p₀ and q₀ such that:

• 1 ≤ p ≤ p₀ ≤ n, 1 ≤ q ≤ q₀ ≤ n,
• p₀ − p + 1 = q₀ − q + 1 = r,
• \(str(p, p₀) = str(q, q₀)\) (in other words, the substring of length \(r\) starting at p equals the substring of length \(r\) starting at q),

then we say that the cocktail at position p and the cocktail at position q are "r-similar". Notice that if two cocktails are "r-similar" for some r ≥ 1, they are automatically "k-similar" for every k such that 0 ≤ k < r. In particular, every pair of distinct cocktails are 0-similar.

The challenge is: For each \(r = 0,1,2,\dots, n-1\), calculate (1) the number of ways to choose 2 cocktails that are \(r\)-similar, and (2) the maximum deliciousness obtainable by mixing two \(r\)-similar cocktails (i.e. the maximum product \(a_p \times a_q\) among such pairs). If there is no valid pair for a given \(r\) (except for the always valid \(r=0\) case), output the maximum deliciousness as -1.

Input/Output specifications follow below.

inputFormat

The input consists of three lines:

1. An integer n (the number of cocktails).
2. A string s of length n containing lowercase letters; the label of the cocktails in order.
3. n space‐separated integers a₁, a₂, …, aₙ, where aᵢ is the deliciousness of the i-th cocktail.

outputFormat

Output n lines. The i-th line (0 ≤ i ≤ n-1) corresponds to \(r=i\) and contains two space-separated integers: the number of pairs of \(r\)-similar cocktails and the maximum deliciousness product obtainable by mixing two \(r\)-similar cocktails. For any \(r\) (r ≥ 1) for which no valid pair exists, output the maximum product as -1.

sample

4
abac
1 2 3 4

6 12
1 3
0 -1
0 -1