Burrows Wheeler-Transform(BWT) is a useful algorithm in text compression. It takes a string s=s₁...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₁...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₁ with s₂ in lexicographic order. To challenge you, Rikka wants you to compare f(s₁),f(s₂) in lexicographic order.

In lexicographic order, s=s₁...s_n is smaller than t=t₁...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 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.

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