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;
struct aint {
  int n;
  vector<long long> add, mini;
  void init(int _n) {
    n = _n;
    add = mini = vector<long long>(n << 2, 0);
  }
  void upd(int node, int l, int r, int qL, int qR, long long v) {
    if (qL <= l && r <= qR) {
      add[node] += v;
      mini[node] += v;
      return;
    }
    int mid = (l + r) >> 1;
    if (qL <= mid) upd((node << 1), l, mid, qL, qR, v);
    if (qR > mid) upd(((node << 1) | 1), mid + 1, r, qL, qR, v);
    mini[node] = min(mini[(node << 1)], mini[((node << 1) | 1)]) + add[node];
  }
  int last_lower(int node, int l, int r, int qL, int qR, long long up,
                 long long k) {
    if (up + mini[node] > k) return 1000000000;
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int ans = 1000000000;
    if (qR > mid)
      ans =
          last_lower(((node << 1) | 1), mid + 1, r, qL, qR, up + add[node], k);
    if (ans != 1000000000) return ans;
    return last_lower((node << 1), l, mid, qL, qR, up + add[node], k);
  }
  long long get_val(int node, int l, int r, int pos) {
    if (l == r) return add[node];
    int mid = (l + r) >> 1;
    if (pos <= mid) return add[node] + get_val((node << 1), l, mid, pos);
    return add[node] + get_val(((node << 1) | 1), mid + 1, r, pos);
  }
};
long long bonus = 2LL * 1000000000;
long long n, k, d, i, j, ans_l, ans_r;
long long a[200011], data[200011], far[200011];
map<long long, bool> M;
stack<pair<long long, long long> > maxi, mini;
aint work;
void solve_zero() {
  int l, r;
  int i, j;
  l = r = 1;
  for (i = 1; i <= n; i = j) {
    for (j = i; j <= n; j++)
      if (a[i] != a[j]) break;
    if (j - i > r - l + 1) {
      l = i;
      r = j - 1;
    }
  }
  printf("%d %d", l, r);
  exit(0);
}
void solve(int l, int r) {
  long long i, j, dim;
  dim = r - l + 1;
  for (i = l; i <= r; i++) data[i - l + 1] = a[i] / d;
  M.clear();
  for (i = j = 1; i <= dim; i++) {
    j = max(i, j);
    M[data[i]] = true;
    while (j + 1 <= dim && M[data[j + 1]] == false) {
      j++;
      M[data[j]] = true;
    }
    far[i] = j;
    M[data[i]] = false;
  }
  while (!maxi.empty()) maxi.pop();
  while (!mini.empty()) mini.pop();
  work.init(dim);
  for (i = dim; i >= 1; i--) {
    pair<long long, long long> act = make_pair(i, i);
    while (!maxi.empty()) {
      auto who = maxi.top();
      if (data[i] <= data[who.first]) break;
      work.upd(1, 1, dim, who.first, who.second, data[i] - data[who.first]);
      act.second = who.second;
      maxi.pop();
    }
    maxi.push(act);
    work.upd(1, 1, dim, i, i, data[i]);
    act = make_pair(i, i);
    while (!mini.empty()) {
      auto who = mini.top();
      if (data[i] >= data[who.first]) break;
      work.upd(1, 1, dim, who.first, who.second, data[who.first] - data[i]);
      act.second = who.second;
      mini.pop();
    }
    mini.push(act);
    work.upd(1, 1, dim, i, i, -data[i]);
    j = work.last_lower(1, 1, dim, i, far[i], 0, k);
    if (j - i + 1 > ans_r - ans_l + 1) {
      ans_l = l + i - 1;
      ans_r = l + j - 1;
    }
    if (j - i + 1 == ans_r - ans_l + 1 && l + i - 1 < ans_l) {
      ans_l = l + i - 1;
      ans_r = l + j - 1;
    }
    work.upd(1, 1, dim, i, dim, -1);
  }
}
int main() {
  scanf("%lld%lld%lld", &n, &k, &d);
  if (d != 0) bonus -= bonus % d;
  for (i = 1; i <= n; i++) scanf("%lld", &a[i]), a[i] += bonus;
  if (d == 0) solve_zero();
  ans_l = ans_r = 1;
  for (i = 1; i <= n; i = j) {
    for (j = i; j <= n; j++)
      if (a[i] % d != a[j] % d) break;
    solve(i, j - 1);
  }
  printf("%lld %lld", ans_l, ans_r);
  return 0;
}
