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 N = 1e6 + 9, INF = 1e18;
long long a[N], seg[N], lazy[N], f[N];
stack<long long> mn, mx;
unordered_map<long long, long long> mp;
void FLUSH(long long pos, long long l, long long r) {
  seg[pos] += lazy[pos];
  if (l != r) {
    lazy[pos * 2] += lazy[pos];
    lazy[pos * 2 + 1] += lazy[pos];
  }
  lazy[pos] = 0;
}
void ADD(long long pos, long long l, long long r, long long ql, long long qr,
         long long val) {
  FLUSH(pos, l, r);
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    lazy[pos] += val;
    FLUSH(pos, l, r);
    return;
  }
  long long mid = (l + r) / 2;
  ADD(pos * 2, l, mid, ql, qr, val);
  ADD(pos * 2 + 1, mid + 1, r, ql, qr, val);
  seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]);
}
long long GET(long long pos, long long l, long long r, long long val) {
  FLUSH(pos, l, r);
  if (l == r) return l;
  if (seg[pos] > val) return 0;
  long long mid = (l + r) / 2;
  FLUSH(pos * 2, l, mid);
  FLUSH(pos * 2 + 1, mid + 1, r);
  if (seg[pos * 2 + 1] <= val)
    return GET(pos * 2 + 1, mid + 1, r, val);
  else
    return GET(pos * 2, l, mid, val);
}
void RUKIDDING(long long n, long long k, long long d) {
  pair<long long, pair<long long, long long> > ans = {0, {0, 0}};
  long long j = 0;
  for (long long i = 0; i < n; i = j) {
    while (j < n && a[i] == a[j]) j++;
    ans = max(ans, {j - i, {-i, j - 1}});
  }
  cout << -ans.second.first + 1 << " " << ans.second.second + 1;
  exit(0);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, k, d;
  cin >> n >> k >> d;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    a[i] += 1e9;
    if (mp.find(a[i]) != mp.end())
      f[i] = max(f[i - 1], mp[a[i]]);
    else
      f[i] = f[i - 1];
    mp[a[i]] = i;
    f[0] = -1;
  }
  if (d == 0) RUKIDDING(n, k, d);
  ADD(1, 0, n - 1, 0, n - 1, +n);
  for (long long i = 1; i < n; i++) ADD(1, 0, n - 1, i, n - 1, -1);
  mn.push(n);
  mx.push(n);
  pair<long long, pair<long long, long long> > ans = {0, {0, 0}};
  long long j = n - 1;
  for (long long i = n - 1; i >= 0; i--) {
    ADD(1, 0, n - 1, 0, n - 1, -1);
    while (f[j] >= i || a[i] % d != a[j] % d) j--;
    while (mx.size() > 1 && a[mx.top()] <= a[i]) {
      long long x = mx.top();
      mx.pop();
      ADD(1, 0, n - 1, x, mx.top() - 1, -(a[x] / d));
    }
    ADD(1, 0, n - 1, i, mx.top() - 1, a[i] / d);
    mx.push(i);
    while (mn.size() > 1 && a[mn.top()] >= a[i]) {
      long long x = mn.top();
      mn.pop();
      ADD(1, 0, n - 1, x, mn.top() - 1, a[x] / d);
    }
    ADD(1, 0, n - 1, i, mn.top() - 1, -(a[i] / d));
    mn.push(i);
    if (j < n - 1) ADD(1, 0, n - 1, j + 1, n - 1, INF);
    ans = max(ans, {GET(1, 0, n - 1, k) - i + 1, {-i, -GET(1, 0, n - 1, k)}});
    ADD(1, 0, n - 1, j + 1, n - 1, -INF);
  }
  cout << -ans.second.first + 1 << " " << -ans.second.second + 1;
  return 0;
}
