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 MAXN = 2 * 100 * 1000 + 17, inf = 2e16 + 17;
long long n, k, d, a[MAXN], mxs[MAXN], mns[MAXN], w[MAXN], dp[MAXN], b[MAXN],
    szseg, seg[MAXN], lazy[MAXN];
long long modu(long long x) { return ((x % d) + d) % d; }
void build(int v = 1, int l = 1, int r = szseg) {
  if (l + 1 == r) {
    seg[v] = b[l];
    return;
  }
  build(v << 1, l, l + r >> 1);
  build(v << 1 | 1, l + r >> 1, r);
  seg[v] = min(seg[v << 1], seg[v << 1 | 1]);
}
void relax(int v) {
  seg[v << 1] += lazy[v];
  seg[v << 1 | 1] += lazy[v];
  lazy[v << 1] += lazy[v];
  lazy[v << 1 | 1] += lazy[v];
  lazy[v] = 0;
}
void add(int lp, int rp, long long val, int v = 1, int l = 1, int r = szseg) {
  if (rp <= l || r <= lp) return;
  if (lp <= l && r <= rp) {
    lazy[v] += val;
    seg[v] += val;
    return;
  }
  relax(v);
  add(lp, rp, val, v << 1, l, l + r >> 1);
  add(lp, rp, val, v << 1 | 1, l + r >> 1, r);
  seg[v] = min(seg[v << 1], seg[v << 1 | 1]);
}
int get(long long val, int v = 1, int l = 1, int r = szseg) {
  if (seg[v] > val) return MAXN;
  if (l + 1 == r) return l;
  relax(v);
  if (seg[v << 1] <= val)
    return get(val, v << 1, l, l + r >> 1);
  else
    return get(val, v << 1 | 1, l + r >> 1, r);
}
long long DC(long long l, long long r) {
  if (r - l == 1) return 1;
  const long long mid = l + r >> 1;
  long long res = max(DC(l, mid), DC(mid, r));
  long long last = mid, ls = w[mid], rast = mid;
  map<long long, bool> mp;
  while (last > l) {
    if (modu(a[last - 1]) == modu(a[last]) && last - 1 != ls)
      last--;
    else
      break;
    ls = max(ls, w[last]);
  }
  last = max(last, w[mid] + 1);
  for (int i = mid; i < r; i++)
    if (!mp[a[i]] && modu(a[i]) == modu(a[mid]))
      rast++, mp[a[i]] = 1;
    else
      break;
  long long mxp = a[mid], mnp = a[mid];
  mns[mid - 1] = mxs[mid - 1] = a[mid - 1];
  for (int i = mid - 2; i >= l; i--)
    mxs[i] = max(a[i], mxs[i + 1]), mns[i] = min(mns[i + 1], a[i]);
  szseg = mid - l + 1;
  for (int i = l; i < mid; i++) {
    b[i - l + 1] = mxs[i] - mns[i] + i * d;
  }
  build();
  for (int i = l; i < last; i++) add(i - l + 1, i - l + 2, inf);
  int pntmn = mid, pntmx = mid;
  for (long long j = mid; j < rast && last < mid; j++) {
    if (pntmn < mid) add(pntmn - l + 1, szseg, mnp - min(mnp, a[j]));
    if (pntmx < mid) add(pntmx - l + 1, szseg, max(mxp, a[j]) - mxp);
    mxp = max(a[j], mxp);
    mnp = min(a[j], mnp);
    while (pntmn > last && mnp < mns[pntmn - 1])
      pntmn--, add(pntmn - l + 1, pntmn - l + 2, mns[pntmn] - mnp);
    while (pntmx > last && mxp > mxs[pntmx - 1])
      pntmx--, add(pntmx - l + 1, pntmx - l + 2, mxp - mxs[pntmx]);
    int gt = get(k * d + j * d);
    if (gt != MAXN) res = max(res, j - l + 1 - gt + 1);
    for (int i = last; i < min(w[j + 1] + 1, mid); i++)
      add(i - l + 1, i - l + 2, inf);
    last = max(last, w[j + 1] + 1);
  }
  for (int i = 1; i <= szseg << 2; i++) seg[i] = lazy[i] = 0;
  return res;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k >> d;
  map<long long, long long> mp;
  for (long long i = 1; i <= n; i++)
    cin >> a[i], w[i] = mp[a[i]], mp[a[i]] = i, b[i] = a[i];
  if (d == 0) {
    long long len = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
      if (a[i - 1] == a[i])
        dp[i] = dp[i - 1] + 1, len = max(len, dp[i]);
      else
        dp[i] = 1;
    for (int i = 1; i <= n; i++)
      if (dp[i] == len) {
        cout << i - len + 1 << ' ' << i << endl;
        break;
      }
    return 0;
  }
  long long len = DC(1, n + 1), l = 0, r = 0;
  multiset<long long> mxmn;
  map<long long, long long> md, nm;
  long long mod = 0, num = 0;
  for (int i = 1; i <= len; i++) {
    md[modu(a[i])]++, nm[a[i]]++;
    if (nm[a[i]] == 1) num++;
    if (md[modu(a[i])] == 1) mod++;
    mxmn.insert(a[i]);
  }
  for (int i = 1; i <= n - len + 1; i++) {
    if (mod == 1 && num == len &&
        k * d + d * (i + len - 1) >= *mxmn.rbegin() - *mxmn.begin() + d * i) {
      l = i, r = i + len - 1;
      break;
    }
    nm[a[i]]--;
    if (nm[a[i]] == 0) num--;
    mxmn.erase(mxmn.find(a[i]));
    md[modu(a[i])]--;
    if (md[modu(a[i])] == 0) mod--;
    md[modu(a[i + len])]++;
    if (md[modu(a[i + len])] == 1) mod++;
    nm[a[i + len]]++;
    if (nm[a[i + len]] == 1) num++;
    mxmn.insert(a[i + len]);
  }
  cout << l << ' ' << r << endl;
  return 0;
}
