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 long long int MOD = 1000000007;
const long long BIG = 1446803456761533460LL;
const int Big = 336860180;
const long long int INF = LONG_LONG_MAX;
const long long int adj4[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
const long long int adj8[8][2] = {{0, 1},   {0, -1}, {1, 0},  {-1, 0},
                                  {-1, -1}, {1, -1}, {-1, 1}, {1, 1}};
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
long long int powMod(long long int a, long long int b) {
  long long int n = 1;
  long long int p = a;
  while (b > 0) {
    if (b % 2 == 1) {
      n *= p;
      n %= MOD;
    }
    p *= p;
    p %= MOD;
    b /= 2;
  }
  return n;
}
long long int modularInverse(long long int a) { return powMod(a, MOD - 2); }
stringstream sss;
const long long int maxn = 200010;
const long long int maxa = 1000000010;
long long int n;
long long int ar[maxn];
long long int prv[maxn];
map<long long int, long long int> lst;
pair<long long int, long long int> seg[maxn * 4];
long long int lazy[maxn * 4];
void build(long long int x = 1, long long int l = 0, long long int r = n) {
  lazy[x] = 0;
  seg[x] = {l, l};
  if (r - l > 1) {
    long long int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid, r);
  }
}
void merge(long long int x) {
  if (seg[x * 2].first <= seg[x * 2 + 1].first) {
    seg[x] = seg[x * 2];
  } else {
    seg[x] = seg[x * 2 + 1];
  }
}
void push(long long int x) {
  seg[x * 2].first += lazy[x];
  lazy[x * 2] += lazy[x];
  seg[x * 2 + 1].first += lazy[x];
  lazy[x * 2 + 1] += lazy[x];
  lazy[x] = 0;
}
void add(long long int li, long long int ri, long long int v,
         long long int x = 1, long long int l = 0, long long int r = n) {
  if (li >= r || l >= ri) {
  } else if (li <= l && r <= ri) {
    seg[x].first += v;
    lazy[x] += v;
  } else {
    if (lazy[x]) {
      push(x);
    }
    long long int mid = (l + r) / 2;
    add(li, ri, v, x * 2, l, mid);
    add(li, ri, v, x * 2 + 1, mid, r);
    merge(x);
  }
}
long long int binarysearch(long long int v, long long int x = 1,
                           long long int l = 0, long long int r = n) {
  if (r - l == 1) {
    return l;
  } else {
    if (lazy[x]) {
      push(x);
    }
    long long int mid = (l + r) / 2;
    if (seg[x * 2].first <= v) {
      return binarysearch(v, x * 2, l, mid);
    } else {
      return binarysearch(v, x * 2 + 1, mid, r);
    }
  }
}
void extr(long long int x = 1, long long int l = 0, long long int r = n) {
  if (r - l == 1) {
    cout << seg[x].first << ' ';
  } else {
    if (lazy[x]) {
      push(x);
    }
    long long int mid = (l + r) / 2;
    extr(x * 2, l, mid);
    extr(x * 2 + 1, mid, r);
  }
}
void MAIN() {
  long long int N, k, d;
  cin >> N >> k >> d;
  for (long long int i = (0); i < (N); ++i) {
    cin >> ar[i];
    ar[i] += maxa;
    prv[i] = lst.count(ar[i]) ? lst[ar[i]] : -1;
    lst[ar[i]] = i;
  }
  long long int best = 0;
  long long int besti;
  if (d == 0) {
    long long int i = 0;
    while (i < N) {
      long long int j = i;
      while (j < N && ar[i] == ar[j]) ++j;
      if (j - i > best) {
        best = j - i;
        besti = i;
      }
      i = j;
    }
    cout << (besti + 1) << ' ' << (besti + best) << '\n';
    return;
  }
  long long int lt = 0;
  while (lt < N) {
    long long int rt = lt;
    while (rt < N && ar[rt] % d == ar[lt] % d) ++rt;
    n = rt - lt;
    for (long long int i = (lt); i < (rt); ++i) {
      ar[i] /= d;
    }
    build();
    add(0, n, -k);
    stack<long long int> mns, mxs;
    long long int ptr = lt;
    for (long long int i = (lt); i < (rt); ++i) {
      while (ptr <= prv[i]) {
        add(ptr - lt, ptr - lt + 1, BIG);
        ++ptr;
      }
      long long int v = ar[i];
      while (!mxs.empty() && v > ar[mxs.top()]) {
        long long int a = mxs.top();
        mxs.pop();
        long long int b = mxs.empty() ? 0 : mxs.top() + 1 - lt;
        add(b, a - lt + 1, -ar[a]);
      }
      add(mxs.empty() ? 0 : mxs.top() + 1 - lt, i + 1 - lt, v);
      mxs.push(i);
      while (!mns.empty() && v < ar[mns.top()]) {
        long long int a = mns.top();
        mns.pop();
        long long int b = mns.empty() ? 0 : mns.top() + 1 - lt;
        add(b, a - lt + 1, ar[a]);
      }
      add(mns.empty() ? 0 : mns.top() + 1 - lt, i + 1 - lt, -v);
      mns.push(i);
      long long int mnlt = binarysearch(0) + lt;
      long long int len = i - mnlt + 1;
      if (seg[1].first <= 0 && (len > best || len == best && mnlt < besti)) {
        best = len;
        besti = mnlt;
      }
      add(0, n, -1);
    }
    lt = rt;
  }
  cout << (besti + 1) << ' ' << (besti + best) << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
6 2 1
-4 -3 -2 -8 -6 -2
    )";
  MAIN();
  return 0;
}
