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 MOD = 1e9 + 7;
const int C = 26;
void add(int &x, int y) {
  x += y;
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
}
int fix(int x) {
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
  return x;
}
int pw(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % MOD;
    b >>= 1;
    a = 1ll * a * a % MOD;
  }
  return ret;
}
const int MAXN = 2e5 + 10;
const long long INF = 1e18;
long long n, k, d, a[MAXN], nxt[MAXN];
long long st[MAXN << 2], lz[MAXN << 2];
void weed(int v) {
  for (int u : {v << 1, v << 1 ^ 1}) {
    lz[u] += lz[v];
    st[u] += lz[v];
  }
  lz[v] = 0;
}
void water(int v, int b, int e, int l, int r, long long val) {
  if (l >= r) return;
  if (b == l && e == r) {
    st[v] += val;
    lz[v] += val;
    return;
  }
  weed(v);
  int m = (b + e) >> 1;
  water(v << 1, b, m, l, min(r, m), val);
  water(v << 1 ^ 1, m, e, max(l, m), r, val);
  st[v] = min(st[v << 1], st[v << 1 ^ 1]);
}
long long smoke(int v, int b, int e, int l, int r) {
  if (l >= r) return INF;
  if (b == l && e == r) return st[v];
  weed(v);
  int m = (b + e) >> 1;
  return min(smoke(v << 1, b, m, l, min(r, m)),
             smoke(v << 1 ^ 1, m, e, max(m, l), r));
}
int descend(int v, int b, int e) {
  if (e - b == 1) {
    return st[v] <= k ? b : -1;
  }
  weed(v);
  int m = (b + e) >> 1;
  long long right = st[v << 1 ^ 1];
  if (right <= k) return descend(v << 1 ^ 1, m, e);
  return descend(v << 1, b, m);
}
void solve() {
  cin >> n >> k >> d;
  for (int i = 0; i < n; i++) cin >> a[i];
  if (d == 0) {
    int start = 0, len = 1;
    for (int l = 0, r = 0; l < n; l++) {
      while (r < n && a[r] == a[l]) ++r;
      if (r - l > len) {
        len = r - l;
        start = l;
      }
    }
    cout << start + 1 << " " << start + len << "\n";
    return;
  }
  long long small = *min_element(a, a + n);
  for (int i = 0; i < n; i++) a[i] -= small;
  map<long long, int> mp;
  for (int i = n - 1; ~i; --i) {
    nxt[i] = i + 1;
    if (i + 1 < n && a[i] % d == a[i + 1] % d) {
      nxt[i] = nxt[i + 1];
    }
    nxt[i] = min(nxt[i], mp.count(a[i]) ? mp[a[i]] : n);
    mp[a[i]] = i;
  }
  for (int i = 0; i < n; i++) a[i] /= d;
  int start = n - 1, len = 1;
  stack<int> mn, mx;
  mn.push(n);
  mx.push(n);
  for (int l = n - 1; ~l; --l) {
    while ((int)mn.size() > 1 && a[l] < a[mn.top()]) {
      int i = mn.top();
      mn.pop();
      water(1, 0, n, i, mn.top(), a[i]);
    }
    while ((int)mx.size() > 1 && a[l] > a[mx.top()]) {
      int i = mx.top();
      mx.pop();
      water(1, 0, n, i, mx.top(), -a[i]);
    }
    water(1, 0, n, l, mn.top(), -a[l]);
    water(1, 0, n, l, mx.top(), a[l]);
    water(1, 0, n, l + 1, n, -1);
    water(1, 0, n, nxt[l], n, INF);
    int r = descend(1, 0, n);
    water(1, 0, n, nxt[l], n, -INF);
    if (r - l + 1 >= len) {
      len = r - l + 1;
      start = l;
    }
    mn.push(l);
    mx.push(l);
  }
  cout << start + 1 << " " << start + len << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int te = 1;
  for (int w = 1; w <= te; w++) {
    solve();
  }
  return 0;
}
