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 = 3e5 + 123;
const int mod = 1e9 + 9;
int n;
long long k, d;
int a[maxn];
int m;
int L[maxn];
long long t[maxn * 4];
long long ad[maxn * 4];
void build(int v, int l, int r) {
  ad[v] = 0;
  t[v] = 0;
  if (l == r) {
  } else {
    int mid = (l + r) / 2;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
  }
}
void push(int v, int tl, int tr) {
  if (tl == tr) return;
  t[v * 2] += ad[v];
  t[v * 2 + 1] += ad[v];
  ad[v * 2] += ad[v];
  ad[v * 2 + 1] += ad[v];
  ad[v] = 0;
}
int get(int v, int tl, int tr, int l, int r, long long k) {
  push(v, tl, tr);
  if (tl > r || l > tr) {
    return -1;
  }
  if (t[v] > k) {
    return -1;
  }
  if (tl == tr) {
    return tl;
  }
  int mid = (tl + tr) / 2;
  int res = get(v * 2, tl, mid, l, r, k);
  if (res != -1) return res;
  return get(v * 2 + 1, mid + 1, tr, l, r, k);
}
void add(int v, int tl, int tr, int l, int r, long long d) {
  push(v, tl, tr);
  if (tl > r || l > tr) {
    return;
  }
  if (l <= tl && tr <= r) {
    t[v] += d;
    ad[v] += d;
    return;
  }
  int mid = (tl + tr) / 2;
  add(v * 2, tl, mid, l, r, d);
  add(v * 2 + 1, mid + 1, tr, l, r, d);
  t[v] = min(t[v * 2], t[v * 2 + 1]);
}
pair<int, int> calc(vector<int> b) {
  m = b.size();
  map<int, int> c;
  for (int i = 0; i < m; i++) {
    if (c.count(b[i]) == 0) {
      L[i] = 0;
    } else {
      L[i] = c[b[i]] + 1;
    }
    c[b[i]] = i;
  }
  for (int i = 1; i < m; i++) {
    L[i] = max(L[i], L[i - 1]);
  }
  build(1, 0, m - 1);
  vector<int> mx;
  vector<int> mi;
  pair<int, int> ans = make_pair(0, 0);
  for (int i = 0; i < m; i++) {
    while (mx.size() > 0 && b[mx.back()] < b[i]) {
      int cur = mx.back();
      mx.pop_back();
      if (mx.size() > 0) {
        add(1, 0, m - 1, mx.back() + 1, cur, -b[cur]);
      } else {
        add(1, 0, m - 1, 0, cur, -b[cur]);
      }
    }
    if (mx.size() > 0) {
      add(1, 0, m - 1, mx.back() + 1, i, b[i]);
    } else {
      add(1, 0, m - 1, 0, i, b[i]);
    }
    mx.push_back(i);
    while (mi.size() > 0 && b[mi.back()] > b[i]) {
      int cur = mi.back();
      mi.pop_back();
      if (mi.size() > 0) {
        add(1, 0, m - 1, mi.back() + 1, cur, b[cur]);
      } else {
        add(1, 0, m - 1, 0, cur, b[cur]);
      }
    }
    if (mi.size() > 0) {
      add(1, 0, m - 1, mi.back() + 1, i, -b[i]);
    } else {
      add(1, 0, m - 1, 0, i, -b[i]);
    }
    mi.push_back(i);
    int cnt = i - get(1, 0, m - 1, L[i], i, k) + 1;
    if (ans.first < cnt) {
      ans.first = cnt;
      ans.second = i;
    }
    add(1, 0, m - 1, 0, i, -1);
  }
  return ans;
}
void solve() {
  cin >> n >> k >> d;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int mi = *min_element(a, a + n);
  for (int i = 0; i < n; i++) {
    a[i] -= mi;
  }
  pair<int, int> ans = make_pair(0, 0);
  if (d == 0) {
    int cnt = 1;
    for (int i = 1; i < n; i++) {
      if (a[i] != a[i - 1]) {
        if (ans.first < cnt) {
          ans.first = cnt;
          ans.second = i - 1;
        }
        cnt = 1;
      } else {
        cnt++;
      }
    }
    if (ans.first < cnt) {
      ans.first = cnt;
      ans.second = n - 1;
    }
    cout << ans.second - ans.first + 2 << " " << ans.second + 1 << "\n";
    return;
  }
  for (int i = 0; i < n;) {
    int j = i;
    vector<int> cur;
    while (i < n && a[j] % d == a[i] % d) {
      cur.push_back(a[i] / d);
      i++;
    }
    pair<int, int> res = calc(cur);
    res.second += j;
    if (res.first > ans.first) {
      ans = res;
    }
  }
  cout << ans.second - ans.first + 2 << " " << ans.second + 1 << "\n";
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}
