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 linf = 1e18 + 5;
const int mod = (int)1e9 + 7;
const int logN = 18;
const int inf = 1e9;
const int N = 2e5 + 333;
int L[N << 2], mn[N << 2], R[N], a[N];
int n, m, l, r, ans, k, d;
map<int, int> h;
void push(int k) {
  mn[(k + k)] += L[k];
  mn[(k + k + 1)] += L[k];
  L[(k + k)] += L[k];
  L[(k + k + 1)] += L[k];
  L[k] = 0;
}
void update(int k, int bas, int son, int x, int y, int t) {
  if (bas > y || son < x) return;
  if (x <= bas && son <= y) {
    L[k] += t;
    mn[k] += t;
    return;
  }
  push(k);
  update((k + k), bas, (bas + son >> 1), x, y, t);
  update((k + k + 1), (bas + son >> 1) + 1, son, x, y, t);
  mn[k] = min(mn[(k + k)], mn[(k + k + 1)]);
}
int query(int k, int bas, int son, int x, int y) {
  if (bas > y || son < x || mn[k] > ::k) return -1;
  if (bas == son) return (mn[k] <= ::k) ? bas : -1;
  push(k);
  int r = query((k + k + 1), (bas + son >> 1) + 1, son, x, y);
  if (r != -1) return r;
  return query((k + k), bas, (bas + son >> 1), x, y);
}
int main() {
  scanf("%d %d %d", &n, &k, &d);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  if (d == 0) {
    int j = 1;
    for (int i = 1; i <= n; i++) {
      while (j <= n && a[i] == a[j]) j++;
      if (j - i > ans) {
        ans = j - i;
        l = i, r = j - 1;
      }
    }
    return cout << l << ' ' << r << '\n', 0;
  } else {
    stack<pair<int, pair<int, int> > > Smax, Smin;
    Smax.push(make_pair(-inf, make_pair(n + 1, n + 1)));
    Smin.push(make_pair(+inf, make_pair(n + 1, n + 1)));
    int j = 1;
    for (int i = 1; i <= n; i++) {
      while (j <= n && abs(a[i] - a[j]) % d == 0 && !h[a[j]]) h[a[j++]] = true;
      R[i] = j - 1;
      h[a[i]] = false;
    }
    for (int i = n; i >= 1; i--) {
      a[i] /= d;
      int fmax = i, fmin = i;
      while (Smax.size() && Smax.top().first <= a[i]) {
        fmax = Smax.top().second.second;
        update(1, 1, n, Smax.top().second.first, Smax.top().second.second,
               -Smax.top().first + a[i]);
        Smax.pop();
      }
      while (Smin.size() && Smin.top().first >= a[i]) {
        fmin = Smin.top().second.second;
        update(1, 1, n, Smin.top().second.first, Smin.top().second.second,
               Smin.top().first - a[i]);
        Smin.pop();
      }
      Smax.push(make_pair(a[i], make_pair(i, fmax)));
      Smin.push(make_pair(a[i], make_pair(i, fmin)));
      int t = query(1, 1, n, i, R[i]);
      if (t != -1 && t - i + 1 >= ans) {
        ans = t - i + 1;
        l = i, r = t;
      }
      update(1, 1, n, i, n, -1);
    }
    return cout << l << ' ' << r << '\n', 0;
  }
  return 0;
}
