说明

科学家记录了连续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]这一段时间的平均气温最高。

输入格式

多组测试数据。

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

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

输出格式

共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

提示