Burrows Wheeler-Transform(BWT) is a useful algorithm in text compression. It takes a string s=s
1...s
n and returns another string with the same length. The algorithm has the following steps:
1. Generate all cyclic shift strings of s. Formally, for each i ∈ [0,n), let t
i = s
i+1...s
ns
1...s
i 2. Sort all t
i in lexicographic order.
3. Generate the result string in which the ith char is equal to the last char of the ith smallest string.
For example, if

, then

, the result of sorting will be

, and the result string will be

.
Let f(s) be the result string we can get when we do BWT on s.
Now, Rikka gets a \textbf{random} 01 string s of length n and m random queries (l
1,i,r
1,i,l
2,i,r
2,i). For each query, let

. Rikka knows it is easy to compare s
1 with s
2 in lexicographic order. To challenge you, Rikka wants you to compare f(s
1),f(s
2) in lexicographic order.
In lexicographic order, s=s
1...s
n is smaller than t=t
1...t
m if and only if they meet at least one of the following two conditions:
1. s is a prefix of t and n < m.
2. there is an
%5D)
which satisfies for all index j ∈ [1,i), s
j = t
j and s
i < t
i.
输入描述:
The first line contains a single integer t(1 ≤ t ≤ 3), the numebr of testcases.
For each testcase, the first line contains three numbers n,m,s(1 ≤ n,m ≤ 105, 0≤ s ≤ 109).
The input is generated by the seed s in the following steps:
1. Let A be a random number array of length 106 in which A0=s,
.
2.
,
.
3.
, let
, then
,
,
,
.
输出描述:
For each query, if f(s1) is smaller than f(s2), output -1, if f(s1) is larger than f(s2), output 1. Otherwise output 0.
示例1
输出
复制
-1
0
1
-1
-1
1
1
1
-1
1
-1
-1
1
-1
-1
1
1
1
-1
1
1
-1
1
1
-1
说明
In the first testcase, string s is equal to 10111.
The queries are (3,3,2,4),(1,2,2,3),(1,4,3,5),(4,5,2,4),(3,4,3,5).