Rikka with Burrow-Wheeler Transform
题号:NC17688
时间限制:C/C++/Rust/Pascal 10秒,其他语言20秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Burrows Wheeler-Transform(BWT) is a useful algorithm in text compression. It takes a string s=s1...sn 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 ti = si+1...sns1...si
2. Sort all ti 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 (l1,i,r1,i,l2,i,r2,i). For each query, let . Rikka knows it is easy to compare s1 with s2 in lexicographic order. To challenge you, Rikka wants you to compare f(s1),f(s2) in lexicographic order.

In lexicographic order, s=s1...sn is smaller than t=t1...tm 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 which satisfies for all index j ∈ [1,i), sj = tj and si < ti.

输入描述:

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

输入

复制
2
5 5 0
100000 20 0

输出

复制
-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).