VelocityX

Caitlin snow is extemely upset upon the events of Escape from Earth2. Zoom took away Jay Garrick from her. Now she wants to seek revenge against Zoom, so she is trying to come up with VelocityX serum which will increase the speed of Barry Allen aka The Flash. She creates the serum using the components 'X', 'Y' and 'Z'. The serum is composed of a sequence of these components and it's effect on Barry depends upon the the sequence interval, which is defined as the difference between the length of the longest substring with equal number of X's,Y's and Z's and the length of the shortest substring with equal number of X's,Y's and Z's. More the sequence interval, faster he will run. She creates a number of sequences and tries to find the sequence interval for all the sequences. As the number of sequences are large, she plans to come up with an algorithm to find the sequence intervals efficiently and to find the maximum sequence interval out of all the sequences generated. Cisco and Harry are busy in developing a trap for Zoom and Felicity is stuck with team Arrow to find about Genesis, so please assist Cait in finding the sequence interval and do it fast coz ZOOM IS COMING.
Input
The first line of the input consists of the number of sequences 'n' (2 <= n <= 1000).
The next 'n' lines consist of a string 's' (3 <= length <= 10000) describing the sequence. The string will have only the alphabets 'X','Y' and 'Z'.
Output
Output 'n' lines containing the sequence distance(interval) of the correspondng input string 's'.
The 'n+1' th line contains the index (1based) of the string with the maximum sequence distance. If multiple strings have maximum sequence distance then output the
index of the one that appears first in the input.
Example
Sample Input 3 XYZXYZXYZ XXYYZZXYZ XXXYYYZZZ Sample Output 6 6 0 1
Explanation
In the given sample case,
for string XYZXYZXYZ (1) Longest = 9 Shortest = 3 Sequence distance = 6
for string XXYYZZXYZ (2) Longest = 9 Shortest = 3 Sequence distance = 6
for string XXXYYYZZZ (3) Longest = 9 Shortest = 9 Sequence distance = 0
(1) and (2) have the maximum value so n+1th line contains 1.
Author:  lakshmi8 
Tags  lakshmi8 
Date Added:  19022016 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 