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>
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
using db = long double;
using ull = unsigned long long;
const int N = 2e5 + 5, MOD = 1e9 + 7;
int n, k, d;
ll t[N << 2], lz[N << 2];
void push(int node, int s, int e) {
  t[node] += lz[node];
  if (s != e) {
    lz[node << 1] += lz[node];
    lz[node << 1 | 1] += lz[node];
  }
  lz[node] = 0;
}
void upd(int node, int s, int e, int l, int r, ll v) {
  push(node, s, e);
  if (r < s || e < l) return;
  if (l <= s && e <= r) {
    lz[node] += v;
    push(node, s, e);
    return;
  }
  int md = (s + e) >> 1;
  upd(node << 1, s, md, l, r, v);
  upd(node << 1 | 1, md + 1, e, l, r, v);
  t[node] = max(t[node << 1], t[node << 1 | 1]);
}
int qry(int node, int s, int e) {
  push(node, s, e);
  if (t[node] < 0) return 0;
  if (s == e) return s;
  int md = (s + e) >> 1;
  int x = qry(node << 1 | 1, md + 1, e);
  if (x) return x;
  return qry(node << 1, s, md);
}
int offset = 0;
pair<int, int> ans = {1, 0};
void solve(vector<int> a) {
  if (a.empty()) return;
  for (auto& x : a) {
    x /= d;
  }
  int sz = a.size();
  map<int, int> mp;
  vector<int> nxtA(sz);
  for (int i = sz - 1; i >= 0; --i) {
    if (mp.count(a[i]) == 0) {
      nxtA[i] = sz;
    } else
      nxtA[i] = mp[a[i]];
    mp[a[i]] = i;
  }
  fill(t, t + 4 * sz, k - 1);
  fill(lz, lz + 4 * sz, 0);
  vector<int> mnStack, mxStack;
  int limit = sz;
  for (int i = sz - 1; i >= 0; --i) {
    upd(1, 0, sz - 1, i, sz - 1, 1);
    int prv = 0;
    while (mxStack.size() && a[i] > a[mxStack.back()]) {
      int idx = mxStack.back();
      mxStack.pop_back();
      upd(1, 0, sz - 1, idx, sz - 1, (a[idx] - prv));
      prv = a[idx];
    }
    if (mxStack.size()) {
      int idx = mxStack.back();
      upd(1, 0, sz - 1, mxStack.back(), sz - 1,
          (a[idx] - prv) - (a[idx] - a[i]));
    }
    prv = 0;
    while (mnStack.size() && a[i] < a[mnStack.back()]) {
      int idx = mnStack.back();
      mnStack.pop_back();
      upd(1, 0, sz - 1, idx, sz - 1, -(a[idx] - prv));
      prv = a[idx];
    }
    if (mnStack.size()) {
      int idx = mnStack.back();
      upd(1, 0, sz - 1, idx, sz - 1, (a[idx] - a[i]) - (a[idx] - prv));
    }
    while (limit > nxtA[i]) {
      upd(1, 0, sz - 1, --limit, sz - 1, INT_MIN);
    }
    mxStack.push_back(i);
    mnStack.push_back(i);
    int mx = qry(1, 0, sz - 1) - i + 1;
    ans = max(ans, make_pair(mx, -(i + offset)));
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k >> d;
  vector<int> v;
  if (d == 0) {
    v.resize(n);
    for (auto& x : v) {
      cin >> x;
    }
    pair<int, int> ans = make_pair(0, -1);
    for (int i = 0, j = 0; i < n; i = j) {
      for (; j < n && v[i] == v[j]; j++)
        ;
      ans = max(ans, make_pair(j - i, -i));
    }
    ans.second *= -1;
    cout << ans.second + 1 << ' ' << ans.second + ans.first << '\n';
    return 0;
  }
  for (int i = 0, cur = -1, x; i < n; i++) {
    cin >> x;
    x += 1000 * 1000 * 1000;
    if (cur != x % d) solve(v), v.clear(), offset = i;
    v.push_back(x);
    cur = x % d;
  }
  solve(v);
  cerr << ans.first << '\n';
  ans.second *= -1;
  cout << ans.second + 1 << ' ' << ans.second + ans.first << '\n';
  return 0;
}
