We'll call a sequence of integers a good k-d sequence if we can add to it at most k numbers in such a way that after the sorting the sequence will be an arithmetic progression with difference d.

You got hold of some sequence a, consisting of n integers. Your task is to find its longest contiguous subsegment, such that it is a good k-d sequence.

Input

The first line contains three space-separated integers n, k, d (1 ≤ n ≤ 2·105; 0 ≤ k ≤ 2·105; 0 ≤ d ≤ 109). The second line contains n space-separated integers: a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the actual sequence.

Output

Print two space-separated integers l, r (1 ≤ l ≤ r ≤ n) show that sequence al, al + 1, ..., ar is the longest subsegment that is a good k-d sequence.

If there are multiple optimal answers, print the one with the minimum value of l.

Examples

Input

6 1 2
4 3 2 8 6 2


Output

3 5

Note

In the first test sample the answer is the subsegment consisting of numbers 2, 8, 6 — after adding number 4 and sorting it becomes sequence 2, 4, 6, 8 — the arithmetic progression with difference 2.
#include <bits/stdc++.h>
using namespace std;
namespace INPUT {
const int L = 1 << 15;
char buffer[L], *S, *T, ch;
inline char Gc() {
  if (S == T) {
    T = (S = buffer) + fread(buffer, 1, L, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
template <class T>
inline void get(T &x) {
  static int f;
  for (ch = Gc(); (ch < '0' || ch > '9') && ch != '-'; ch = Gc())
    ;
  if (ch == '-')
    f = -1, x = 0;
  else
    f = 1, x = ch ^ '0';
  for (ch = Gc(); ch >= '0' && ch <= '9'; ch = Gc()) x = x * 10 + (ch ^ '0');
  x *= f;
}
}  // namespace INPUT
const int N = 200005;
int n, k, d, A[N];
void solve0() {
  int L = 1, R = 1;
  for (int i = 1; i <= n;) {
    int j = i;
    while (A[j] == A[i] && j <= n) j++;
    if (R - L + 1 < j - i) L = i, R = j - 1;
    i = j;
  }
  cout << L << " " << R << endl;
}
map<int, int> H;
int Min[N * 4], Tag[N * 4];
inline void Add(int x, int l, int r, int L, int R, int t) {
  if (L <= l && r <= R)
    Min[x] += t, Tag[x] += t;
  else {
    int Mid = l + r >> 1;
    if (L <= Mid) Add(x << 1, l, Mid, L, R, t);
    if (R > Mid) Add(x << 1 | 1, Mid + 1, r, L, R, t);
    Min[x] = min(Min[x << 1], Min[x << 1 | 1]) + Tag[x];
  }
}
inline int Ask(int x, int l, int r, int L, int R, int t) {
  if (L <= l && r <= R) {
    if (Min[x] > t) return N;
    if (l == r) return l;
    t -= Tag[x];
    int Mid = l + r >> 1;
    if (Min[x << 1] <= t) return Ask(x << 1, l, Mid, L, R, t);
    return Ask(x << 1 | 1, Mid + 1, r, L, R, t);
  }
  t -= Tag[x];
  int Mid = l + r >> 1;
  if (L > Mid) return Ask(x << 1 | 1, Mid + 1, r, L, R, t);
  int Ans = Ask(x << 1, l, Mid, L, R, t);
  if (Ans == N && R > Mid)
    return Ask(x << 1 | 1, Mid + 1, r, L, R, t);
  else
    return Ans;
}
inline int Ask(int x, int l, int r, int p) {
  if (l == r) return Min[x];
  int Mid = l + r >> 1;
  if (p <= Mid) return Ask(x << 1, l, Mid, p) + Tag[x];
  return Ask(x << 1 | 1, Mid + 1, r, p) + Tag[x];
}
void solve(int l, int r, int &L, int &R) {
  static int st1[N], top1, st2[N], top2;
  top1 = top2 = 0;
  st2[0] = st1[0] = l - 1;
  int Pos = l;
  for (int i = l; i <= r; i++) {
    Pos = max(Pos, H[A[i]] + 1);
    H[A[i]] = i;
    A[i] /= d;
    while (top1 && A[st1[top1]] < A[i])
      Add(1, 1, n, st1[top1 - 1] + 1, st1[top1], -A[st1[top1]]), top1--;
    while (top2 && A[st2[top2]] > A[i])
      Add(1, 1, n, st2[top2 - 1] + 1, st2[top2], A[st2[top2]]), top2--;
    Add(1, 1, n, st1[top1] + 1, i, A[i]);
    st1[++top1] = i;
    Add(1, 1, n, st2[top2] + 1, i, -A[i]);
    st2[++top2] = i;
    Add(1, 1, n, Pos, i, -1);
    int j = Ask(1, 1, n, Pos, i, k - 1);
    if (j != N && (R - L < i - j || (R - L == i - j && j < L))) L = j, R = i;
  }
}
void solve1() {
  int L = 1, R = 1;
  for (int i = 1; i <= n;) {
    int j = i;
    while (A[j] % d == A[i] % d && j <= n) j++;
    solve(i, j - 1, L, R);
    i = j;
  }
  cout << L << " " << R << endl;
}
int main() {
  INPUT::get(n);
  INPUT::get(k);
  INPUT::get(d);
  for (int i = 1; i <= n; i++) INPUT::get(A[i]), A[i] += 1e9 + 1;
  if (!d)
    solve0();
  else
    solve1();
  return 0;
}
