### Wine Tasting Conference

The annual "Mirage Pavillion Summer Wine Tasting Conference" has just witnessed its grand opening. The event consisted of a Tasting Challenge and a Fun Challenge, with two prizes awarded to the winners, "Top Sommelier" and "Top Hunter", attracting many tasters to participate.

At the conference dinner, the bartender Rainbow made $$n$$ cocktails. The cocktails were arranged in a row, with the $$i^{th}$$ glass $$(1 \leq i \leq n)$$ labelled one of the 26 lowercase letters of the alphabet $$s_i$$. Let $$Str(l, r)$$ denote the string consisting of the sequentially concatenated $$r - l + 1$$ labels of the the $$l^{th}$$ glass to the $$r^{th}$$ glass. If $$Str(p, p_0) = Str(q, q_0)$$, where $$1 \leq p_0 \leq p \leq n$$, $$1 \leq q_0 \leq q \leq n$$, $$p \neq q$$, and $$p_0 - p + 1 = q_0 - q + 1 = r$$, then the $$p^{th}$$ glass is said to be "$$r$$-alike" to the $$q^{th}$$ glass. Of course, two glasses of wine that are "$$r$$-alike" $$(r > 1)$$ are also "1-alike", "2-alike", and "$$(r - 1)$$-alike". In particular, for any $$1 \leq p$$, $$q \leq n$$, $$p \neq q$$, the $$p^{th}$$ glass is "0-alike" to the $$q^{th}$$ glass.

During the tasting session, Sommelier Freda assessed the tastiness of each drink, and with her professionalism and experience easily won the title of "Top Sommelier". The $$i^{th}$$ drink $$(1 \leq i \leq n)$$ was hence rated $$a_i$$. Rainbow then announced the question for the Fun Challenge: If the $$p^{th}$$ cocktail were to be mixed with the $$q^{th}$$ cocktail, you would get a drink with tastiness $$a_p * a_q$$. He asks the sommeliers: For each $$r = 0, 1, 2, \ldots, n - 1$$, count the number of ways to select two "r-alike" cocktails, and also find the maximum tastiness that can be obtained by blending two "r-alike" cocktails.

### Limits

$$1 \leq n \leq 3 \times 10^5$$, $$1 \leq |a_i| \leq 10^9$$.

1 15 $$n \leq 500$$
$$|a_i| \leq 10000$$
2 25 $$n \leq 2000$$
3 10 $$n \leq 99991$$
No pairs of 10-alike cocktails exist.
4 20 All values of $$a_i$$ are equal.

### Input format

The first line of input consists of a single integer $$n$$, the number of glasses of cocktails.
The second line of input consists of a length $$n$$ string of lowercase letters $$S$$, the $$i^{th}$$ character of which represents glass $$i$$'s label.
The third line of input contains $$n$$, the $$i^{th}$$ of which represents the tastiness $$a_i$$ of cocktail $$i$$.

### Output format

Output $$n$$ lines each containing two integers. On the $$i^{th}$$ line, the first integer shall be the number of ways to choose two $$(i - 1)$$-alike cocktail glasses, and the second integer shall be the greatest tastiness achievable by mixing two $$(i - 1)$$-alike cocktails. If no pairs of $$(i - 1)$$-alike cocktails exist, output 0 for both integers.

### Samples

 Sample Input 1 Sample Output 1 10 ponoiiipoi 2 1 4 7 4 8 3 6 4 7 45 56 10 56 3 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0

• 0-alike: All 45 pairs of cocktails are 0-alike. The tastiest mix has tastiness $$8 \times 7 = 56$$.
• 1-alike: The 1-alike pairs of cocktails are $$(1, 8), (2, 4), (2, 9), (4, 9), (5, 6), (5, 7), (5, 10), (6, 7), (6, 10)$$, and $$(7, 10)$$. The tastiest mix remains $$8 \times 7 = 56$$.
• 2-alike: The 2-alike pairs of cocktails are $$(1, 8), (4, 9)$$, and $$(5, 6)$$. The tastiest of them has tastiness $$4 \times 8 = 32$$.
• No pairs of cocktails are 3-alike, 4-alike, $$\ldots$$, or 9-alike.

 Sample Input 2 Sample Output 2 12 abaabaabaaba 1 -2 3 -4 5 -6 7 -8 9 -10 11 -12 66 120 34 120 15 55 12 40 9 27 7 16 5 7 3 -4 2 -4 1 -4 0 0 0 0

### Compile Errors

Time Limit: 1 Seconds
Memory Limit: 512MB
No. of ACs: 3