Description

科学家记录了连续N的气温，保存在数组a[0...N-1]。气温满足如下规律：

对于所有的0<=i<N,都满足a[i] = ( i * i + 4*i + 7)%M，注意：i*i可能比较大。科学家要种植两类农作物，每类农作物的生长周期都是Y天。

第一类农作物喜欢低温，科学家要在N天中，找到一段连续的Y天，使得这Y天的平均气温是最低的，如果有多种方案满足，科学家希望越早开始种植越好，也就是说：要输出最小的一个下标s,使得a[s...s+Y-1]这一段时间的平均气温最低。

第二类农作物喜欢高温，科学家要在N天中，找到一段连续的Y天，使得这Y天的平均气温是最高的，如果有多种方案满足，科学家希望越迟开始种植越好，也就是说：要输出最大的一个下标t,使得a[t...t+Y-1]这一段时间的平均气温最高。

Input Format

多组测试数据。

第一行，一个正整数G,表示有G组测试数据。1<=G<=5。

第二行，3个整数: N, M,Y。1<=N<=1000000,  1<=M<=1000,  1<=Y<=N。

Output Format

共G行，每行两个整数: s和t。

5
12 20 1
12 20 4
12 1 3
57000 997 23
684468 3 1

8 4
6 2
0 9
984 56322
1 684467