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;
const int MAXN = 1 << 18;
const long long inf = 1e12;
struct Tournament {
  long long T[2 * MAXN];
  long long S[2 * MAXN];
  int offset = MAXN;
  void init(int n) {
    offset = 1;
    while (offset < n) offset *= 2;
    for (int i = 0; i < (2 * offset); ++i) S[i] = 0;
    for (int i = 0; i < (offset); ++i) T[i + offset] = i;
    for (int i = offset - 1; i > 0; --i) T[i] = min(T[i * 2], T[i * 2 + 1]);
  }
  void propagate(int i) {
    int l = i * 2, r = l + 1;
    if (S[i]) {
      S[l] += S[i], S[r] += S[i];
      T[l] += S[i], T[r] += S[i];
      S[i] = 0;
    }
  }
  void merge(int i) {
    int l = i * 2, r = l + 1;
    if (T[l] < T[r])
      T[i] = T[l] + S[i];
    else
      T[i] = T[r] + S[i];
  }
  void inc(int i, int lo, int hi, int a, int b, int k) {
    if (lo >= b || hi <= a) return;
    if (lo >= a && hi <= b) {
      S[i] += k;
      T[i] += k;
      return;
    }
    propagate(i);
    inc(i * 2, lo, (lo + hi) / 2, a, b, k);
    inc(i * 2 + 1, (lo + hi) / 2, hi, a, b, k);
    merge(i);
  }
  void set(int x, long long v) {
    x += offset;
    T[x] = v, S[x] = 0;
    for (int y = x / 2; y; y /= 2) T[x] -= S[y];
    for (x /= 2; x; x /= 2) merge(x);
  }
  int get(int i, int k) {
    if (i >= offset) return i - offset;
    propagate(i);
    if (T[i * 2] <= k) return get(i * 2, k);
    return get(i * 2 + 1, k);
  }
  void inc(int a, int b, int k) { inc(1, 0, offset, a, b, k); }
  int getFirstLess(int k) { return T[1] > k ? -1 : get(1, k); }
} T;
int a[MAXN];
int main(void) {
  int n, k, d;
  scanf("%d %d %d", &n, &k, &d);
  for (int i = 0; i < (n); ++i) scanf("%d", a + i);
  for (int i = 0; i < (n); ++i) a[i] += 1e9;
  auto equal = [&d](int x, int y) {
    return d == 0 ? (x == y) : (x % d) == (y % d);
  };
  T.init(n);
  int lo = 0;
  int ans = 0, ansl = 0;
  while (lo < n) {
    int hi = lo;
    while (hi < n && equal(a[lo], a[hi])) hi++;
    auto updateAns = [&ans, &ansl](int x, int y) {
      if (y - x + 1 > ans) ans = y - x + 1, ansl = x;
    };
    if (d == 0) {
      updateAns(lo, hi - 1);
      lo = hi;
      continue;
    }
    for (int i = lo; i < hi; ++i) a[i] /= d;
    static map<int, int> M;
    M.clear();
    static int Smin[MAXN], Smax[MAXN];
    int cmin = 0, cmax = 0;
    Smin[cmin++] = Smax[cmax++] = -1;
    for (int i = lo; i < hi; ++i) {
      int last = -1;
      if (M.count(a[i])) last = M[a[i]];
      while (lo <= last) T.set(lo, inf), lo++;
      M[a[i]] = i;
      Smin[cmin] = i;
      while (cmin > 1 && a[i] <= a[Smin[cmin - 1]]) {
        T.inc(Smin[cmin - 2] + 1, Smin[cmin - 1] + 1, +a[Smin[cmin - 1]]);
        cmin--;
      }
      Smin[cmin++] = i;
      T.inc(Smin[cmin - 2] + 1, Smin[cmin - 1] + 1, -a[i]);
      Smax[cmax] = i;
      while (cmax > 1 && a[i] >= a[Smax[cmax - 1]]) {
        T.inc(Smax[cmax - 2] + 1, Smax[cmax - 1] + 1, -a[Smax[cmax - 1]]);
        cmax--;
      }
      Smax[cmax++] = i;
      T.inc(Smax[cmax - 2] + 1, Smax[cmax - 1] + 1, +a[i]);
      int f = T.getFirstLess(k + i);
      if (f != -1) updateAns(f, i);
    }
    while (lo < hi) T.set(lo, inf), lo++;
  }
  printf("%d %d\n", ansl + 1, ansl + ans);
  return 0;
}
