9593: Inversion Number Parity

Attention: unusual memory limit for this problem 

An inversion in a sequence is a pair of elements that are out of their natural order, and the inversion number of a permutation P = [p₀, p₁, …, p_n-1] of 0 to (n−1) is the number of pairs (p_i, p_j) such that i < j and p_i > p_j. Given a permutation P = [p₀, p₁, …, p_n-1] and (n−1) modifications [(l₁, r₁, d₁), (l₂, r₂, d₂), …, (l_n-1, r_n-1, d_n-1)], your task is to find out the parity of the inversion number of P before and after each modification. More specifically, the permutation P will have n versions, where the first version is given as above, and for i = 1, 2, …, n−1, the (i+1)-th version is based on the i-th version after shifting the interval between indices l_i and r_i of the permutation circularly left d_i times (check the note for more details), and the parity of the inversion number of P is required for each version. Additionally, since the given n is a bit large, we will generate the permutation P and modifications by the following random generator from the given n, A, B and C instead. 

The random generated sequence [f₀, f₁, …] is defined as:

• ∧ means bitwise-AND, ⊕ means bitwise-XOR, and ⌊x⌋ means rounding x down to the nearest integer;let U = 2³⁰ − 1, and the undermentioned f_x, g_x, h_x are all integers between 0 and U, inclusive;
• let f_-3 = A ∧ U, f_-2 = B ∧ U and f_-1 = C ∧ U;
• for i = 0, 1, …, let g_i = f_i-3 ⊕ ((2¹⁶ f_i-3) ∧ U);
• for i = 0, 1, …, let h_i = g_i ⊕ ⌊g_i/2⁵⌋;
• for i = 0, 1, …, let f_i = h_i ⊕ ((2 h_i) ∧ U) ⊕ f_i-2 ⊕ f_i-1. 

With the above generator,

• x mod y (y > 0) means the remainder of x divided by y;
• the first version of permutation P is derived from [0, 1, …, n−1] after swapping p_i and p_{i+(fi mod (n−i))} for i = 0, 1, …, n−1 sequentially;
• for i = 1, …, n−1, let l_i = min(f_n+3i-3 mod n, f_n+3i-2 mod n), r_i = max(f_n+3i-3 mod n, f_n+3i-2 mod n), d_i = (f_n+3i-1 mod n) + 1.

For each test case, output a string of length $n$ in one line, where the $i$-th character of the string is $0$ if the parity of the inversion number of the $i$-th version of $P$ is even, or $1$ otherwise (i.e. the parity is odd).

· $[0,0,0,0,0,0,0,0,0,\dots ]$;
· $[1,0,202754,1,202755,692070724,692070724,692070725,792595,\dots ]$.
The generated permutations and modifications for all test cases in the example are:
· P=[0,1,2]P = [0, 1, 2]P=[0,1,2], modifications=[(0,0,1),(0,0,1)]\mathrm{modifications} = [(0, 0, 1), (0, 0, 1)]modifications=[(0,0,1),(0,0,1)];
· P=[1,0,2]P = [1, 0, 2]P=[1,0,2], modifications=[(0,1,2),(1,2,2)]\mathrm{modifications} = [(0, 1, 2), (1, 2, 2)]modifications=[(0,1,2),(1,2,2)];
· P=[1,0,2]P = [1, 0, 2]P=[1,0,2], modifications=[(0,2,1),(0,1,2)]\mathrm{modifications} = [(0, 2, 1), (0, 1, 2)]modifications=[(0,2,1),(0,1,2)];
· P=[2,1,0]P = [2, 1, 0]P=[2,1,0], modifications=[(1,1,3),(1,2,3)]\mathrm{modifications} = [(1, 1, 3), (1, 2, 3)]modifications=[(1,1,3),(1,2,3)];
· P=[3,1,2,8,5,0,4,7,6,9]P = [3, 1, 2, 8, 5, 0, 4, 7, 6, 9]P=[3,1,2,8,5,0,4,7,6,9], modifications=[(1,8,2),(0,6,10),(3,5,10),(2,4,2),(7,8,9),(1,2,7),\mathrm{modifications} = [(1, 8, 2), (0, 6, 10), (3, 5, 10), (2, 4, 2), (7, 8, 9), (1, 2, 7),modifications=[(1,8,2),(0,6,10),(3,5,10),(2,4,2),(7,8,9),(1,2,7), $(0,9,2),(8,9,2),(5,7,5)]$.
For the last test case,
· the second version of $P$ is $[3,8,5,0,4,7,6,1,2,9]$, resulting from circularly shifting the interval of indices $[1,8]$ left twice (i.e. $[\dots ,1,2,8,5,0,4,7,6,\dots ]$ $\to$ $[\dots ,2,8,5,0,4,7,6,1,\dots ]$ $\to$ $[\dots ,8,5,0,4,7,6,1,2,\dots ]$);
· the third version of $P$ is $[0,4,7,6,3,8,5,1,2,9]$, resulting from circularly shifting the interval of indices $[0,6]$ left $10$ times (i.e. $[3,8,5,0,4,7,6,\dots ]$ $\to$ $[8,5,0,4,7,6,3,\dots ]$ $\to$ $\cdots$ $\to$ $[0,4,7,6,3,8,5,\dots ]$);
· the inversion numbers of all versions are $13$, $21$, $19$, $19$, $21$, $22$, $23$, $25$, $25$ and $27$ respectively.