Sereja and Random Array

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja likes to generate pseudo random binary sequences. Now Sereja has two generators: one is a based on linear congruential generators (LCGs) and another is based on Xorshift.
Sereja has some binary sequences generated in past times, and he wants to know which generator makes these sequences. You can know the details of Sereja's generators, then can you answer this problem?
The following is the details. We may give the length N and a seed integer S to the generators, then they generate a binary sequence A[1], A[2], ..., A[N].
The 1st generator works as follows (C++ code. If you are not familiar with C++, please see the below section Notes for C++):
/*  start here */ unsigned X; // we assume that unsigned is a 32bit integer type void srand1(unsigned S){ X = S; } unsigned nextInteger1(void){ X = X * 1103515245 + 12345; return (X / 65536) % 32768; } void generator1(int N, unsigned S, int A[]){ srand1(S); for(int i=1;i<=N;i++){ A[i] = nextInteger1() % 2; } } /*  end here */
The 2nd generator works as follows (C++ code):
/*  start here */ unsigned x, y, z, w; // we assume that unsigned is a 32bit integer type void srand2(unsigned S){ x = S; y = x * S; z = y * S; w = z * S; } unsigned nextInteger2(void){ unsigned t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } void generator2(int N, unsigned S, int A[]){ srand2(S); for(int i=1;i<=N;i++){ A[i] = nextInteger2() % 2; } } /*  end here */
Note that the LCG used in the 1st generator is the same one suggested in ISO/IEC 9899 (pp. 346347), and Xorshift used in the 2nd generator is the same one in the paper by Marsaglia (July 2003).
Input
The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.
Each test case has only one line. The line contains the string of length N, denoting the array A[1], A[2], ..., A[N], where the string consists of only characters '0' and '1', and the i^{th} character denotes A[i].
Note that the integer N is not given in the input explicitly.
Output
For each test case, print "LCG" if the given sequence generated by the 1st generator, or print "Xorshift" if the given sequence is generated by the 2nd generator.
Constraints and Subtasks
 1 ≤ T ≤ 30
 There is no pair of integers (s, t) such that 0 ≤ s, t ≤ 10^{9} and both generator1(N, s, A) and generator2(N, t, A) generate the given sequence. (Thus the answer will be determined uniquely)
Subtask 1 (10 points)
 50 ≤ N ≤ 500
 There is an integer 0 ≤ s ≤ 500 such that generator1(N, s, A) or generator2(N, s, A) generates the given sequence.
Subtask 2 (40 points)
 500 ≤ N ≤ 100000
 There is an integer 0 ≤ s ≤ 31313 such that generator1(N, s, A) or generator2(N, s, A) generates the given sequence.
Subtask 3 (20 points)
 100000 ≤ N ≤ 200000
 There is an integer 0 ≤ s ≤ 10^{9} such that generator1(N, s, A) or generator2(N, s, A) generates the given sequence.
Subtask 4 (30 points)
 500 ≤ N ≤ 200000
 There is an integer 0 ≤ s ≤ 10^{9} such that generator1(N, s, A) or generator2(N, s, A) generates the given sequence.
Example
Input: 6 1101100100101111010011010101110100001000000101001110101011010101010 000101101110101101110110010111000000011001101110101 11010100010110001101010110111000010001110010010011011110010010110000001100110 01011010100111100111101001010010100100111000111110 0000000000000000000000001001001010101011001111101101010 11101001010000000111101001111111000010000111010011111000001111 Output: LCG LCG LCG Xorshift Xorshift Xorshift
Explanation
Example 1. generator1(67, 5, A) generates the given sequence.
Example 2. generator1(51, 8, A) generates the given sequence.
Example 3. generator1(77, 58, A) generates the given sequence.
Example 4. generator2(50, 5, A) generates the given sequence.
Example 5. generator2(55, 8, A) generates the given sequence.
Example 6. generator2(62, 58, A) generates the given sequence.
Notes for C++
At first, in the codes, almost every operation will be done with unsigned.
Thus operations will return the result modulo 2^{32}.
For example,
X * 1103515245 + 12345
means that
and
(X / 65536) % 32768
means that
in terms of mathematical notations.
Then there are some bit operations in the 2nd generator.
The operators << and >> denote bit shifts.
For example,
X << 15
means that
and
X >> 13
means that
And the operator ^ denotes bitwise XOR.
Author:  sereja 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/SEAPROAR 
Tags  bitwiseoperatn, march15, medium, seapror, sereja 
Date Added:  29112014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions