科学家记录了连续 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。