Given a string consisting of lowercase English alphabets of length N

Consider each proper prefix of length from 1 to N-1 and compare that prefix with each of the other same-length substrings lexicographically except the prefix itself.

For each prefix of length from 1 to N-1 ,compare that prefix with each of the same length substrings, and determine how many substrings are greater, equal, and smaller than that prefix respectively.

Notes A substring is a contiguous sequence of characters within a string .For example the list of all non-empty substrings of the string "apple" would be "apple", "appl" ,"pple" ,"app", "ppl" ,"ple","ap" ,"pp" ,"pl", "le" ,"a","p" ,"l","e". A prefix of a string S is a substring that occurs at the beginning of S.

Input format:

The fist line consists of an integer N The second fine consists of a string S of length N

Output format Print N-1 lines. The ith line denotes the answers for the prefix length i. Each line will have 3 integers denoting the count of lexicographically greater substrings, equal substrings, and smaller substrings, respectively.

Constraints 2≤ N ≤ 1e5 String S consists of lowercase English letters.

Sample Input: 5 abcba

Sample Output: 3 1 0 3 0 0 2 0 0 1 0 0

I know that the equal strings can be found by using KMP algorithm, but how to solve for lexographically smaller/larger?