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("O2")
using namespace std;
const long long MXN = 2e5 + 10;
const long long MXS = MXN * 4;
const long long INF = 1e9;
long long n, m, k, d, z = 1;
long long A[MXN], B[MXN];
long long Min[MXS], Lazy[MXS];
vector<long long> stk[2];
pair<long long, long long> ans, now;
void Build(long long id = 1, long long s = 1, long long e = m) {
  Min[id] = 0, Lazy[id] = 0;
  if ((e - s + 1) == 1) return;
  Build((id * 2), s, ((s + e) / 2)), Build((id * 2 + 1), ((s + e) / 2 + 1), e);
}
void Shift(long long id, long long s, long long e) {
  if (!Lazy[id]) return;
  Min[id] += Lazy[id];
  if ((e - s + 1) > 1) {
    Lazy[(id * 2)] += Lazy[id];
    Lazy[(id * 2 + 1)] += Lazy[id];
  }
  Lazy[id] = 0;
}
void Upd(long long l, long long r, long long x, long long id = 1,
         long long s = 1, long long e = m) {
  Shift(id, s, e);
  if (e < l || s > r) return;
  if (l <= s && e <= r) {
    Lazy[id] += x;
    Shift(id, s, e);
    return;
  }
  Upd(l, r, x, (id * 2), s, ((s + e) / 2)),
      Upd(l, r, x, (id * 2 + 1), ((s + e) / 2 + 1), e);
  Min[id] = min(Min[(id * 2)], Min[(id * 2 + 1)]);
}
int Get(long long l, long long r, long long id = 1, long long s = 1,
        long long e = m) {
  Shift(id, s, e);
  if (e < l || s > r || Min[id] >= k) return INF;
  if ((e - s + 1) == 1) return s;
  long long val = Get(l, r, (id * 2), s, ((s + e) / 2));
  if (val < INF) {
    Min[id] = min(Min[(id * 2)], Min[(id * 2 + 1)]);
    return val;
  }
  val = Get(l, r, (id * 2 + 1), ((s + e) / 2 + 1), e);
  Min[id] = min(Min[(id * 2)], Min[(id * 2 + 1)]);
  return val;
}
pair<long long, long long> solve(int lef) {
  stk[0].clear(), stk[1].clear();
  stk[0].push_back(0), stk[1].push_back(0);
  Build();
  map<long long, long long> last;
  now = {0, -0};
  long long low = 1;
  for (int i = 1; i <= m; i++) {
    assert(z == 1);
    for (int j = 0; j < 2; j++) {
      while (stk[j].size() > 1 && z * B[stk[j].back()] <= z * B[i]) {
        Upd(stk[j][stk[j].size() - 2] + 1, stk[j].back(),
            z * (B[i] - B[stk[j].back()]));
        stk[j].pop_back();
      }
      stk[j].push_back(i);
      z *= -1;
    }
    low = max(low, last[B[i]] + 1);
    Upd(low, i, -1);
    if (Min[1] < k) {
      long long p = Get(low, m);
      if (p <= i) {
        now = max(now, make_pair(i - p + 1, -(lef + p - 1)));
      }
    }
    last[B[i]] = i;
  }
  return now;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k >> d;
  for (int i = 1; i <= n; i++) cin >> A[i], A[i] += INF;
  if (d == 0) {
    long long ANS = 1, ted = 1, l = 1, r = 1;
    for (int i = 2; i <= n; i++) {
      ted = (A[i] == A[i - 1] ? ted + 1 : 1);
      if (ted > ANS) {
        ANS = ted;
        r = i, l = i - ted + 1;
      }
    }
    return cout << l << ' ' << r << '\n', 0;
  }
  ans = {0, -0};
  for (int l = 1; l <= n; l++) {
    long long r = l, q = d - (A[l] % d);
    while (r + 1 <= n && A[r + 1] % d == A[l] % d) r++;
    for (int i = l; i <= r; i++) {
      B[i - l + 1] = (A[i] + q) / d;
    }
    m = r - l + 1;
    ans = max(ans, solve(l));
    l = r;
  }
  cout << -ans.second << ' ' << -ans.second + ans.first - 1 << '\n';
  return 0;
}
