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 N = 200010;
const long long INF = 0x3F3F3F3F3F3F3F3Fll;
inline void read(int &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x = x * f;
}
struct node {
  long long mi, ma, tagmi, tagma, val;
};
map<int, int> mp;
int n, k, d, a[N], b[N], num, head, tail, top1, stk1[N], top2, stk2[N], ans,
    ansl, ansr;
struct segmenttree {
  node tr[N << 2];
  void pushup(int x) {
    tr[x].mi = min(tr[x << 1].mi, tr[x << 1 | 1].mi);
    tr[x].ma = max(tr[x << 1].ma, tr[x << 1 | 1].ma);
    tr[x].val = min(tr[x << 1].val, tr[x << 1 | 1].val);
  }
  void pushdown(int x) {
    tr[x << 1].mi += tr[x].tagmi;
    tr[x << 1].tagmi += tr[x].tagmi;
    tr[x << 1].val -= tr[x].tagmi;
    tr[x << 1].ma += tr[x].tagma;
    tr[x << 1].tagma += tr[x].tagma;
    tr[x << 1].val += tr[x].tagma;
    tr[x << 1 | 1].mi += tr[x].tagmi;
    tr[x << 1 | 1].tagmi += tr[x].tagmi;
    tr[x << 1 | 1].val -= tr[x].tagmi;
    tr[x << 1 | 1].ma += tr[x].tagma;
    tr[x << 1 | 1].tagma += tr[x].tagma;
    tr[x << 1 | 1].val += tr[x].tagma;
    tr[x].tagmi = tr[x].tagma = 0;
  }
  void build(int x = 1, int l = 1, int r = n) {
    if (l == r) {
      tr[x].mi = tr[x].ma = a[l];
      tr[x].val = l;
      return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  void delet(int p, int x = 1, int l = 1, int r = n) {
    if (l == r) {
      tr[x].val = INF;
      return;
    }
    pushdown(x);
    int mid = l + r >> 1;
    if (p <= mid)
      delet(p, x << 1, l, mid);
    else
      delet(p, x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  void updatemin(int ll, int rr, int v, int x = 1, int l = 1, int r = n) {
    if (ll <= l && r <= rr) {
      tr[x].mi += v;
      tr[x].val -= v;
      tr[x].tagmi += v;
      return;
    }
    pushdown(x);
    int mid = l + r >> 1;
    if (ll <= mid) updatemin(ll, rr, v, x << 1, l, mid);
    if (rr > mid) updatemin(ll, rr, v, x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  void updatemax(int ll, int rr, int v, int x = 1, int l = 1, int r = n) {
    if (ll <= l && r <= rr) {
      tr[x].ma += v;
      tr[x].val += v;
      tr[x].tagma += v;
      return;
    }
    pushdown(x);
    int mid = l + r >> 1;
    if (ll <= mid) updatemax(ll, rr, v, x << 1, l, mid);
    if (rr > mid) updatemax(ll, rr, v, x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  long long quer(int num, int x = 1, int l = 1, int r = n) {
    if (l == r) return l;
    pushdown(x);
    int mid = l + r >> 1;
    if (tr[x << 1].val <= num)
      return quer(num, x << 1, l, mid);
    else
      return quer(num, x << 1 | 1, mid + 1, r);
  }
} T;
int main() {
  int i, j;
  read(n);
  read(k);
  read(d);
  for (i = 1; i <= n; i++) {
    read(a[i]);
    a[i] += 1000000000;
  }
  if (d == 0) {
    ans = 0;
    i = 1;
    while (i <= n) {
      j = i;
      while (j < n && a[j + 1] == a[i]) j++;
      if (j - i + 1 > ans) {
        ans = j - i + 1;
        ansl = i;
        ansr = j;
      }
      i = j + 1;
    }
    printf("%d %d\n", ansl, ansr);
    return 0;
  }
  i = 1;
  while (i <= n) {
    j = i;
    b[i] = i;
    while (j < n && a[j + 1] % d == a[i] % d) j++, b[j] = i;
    i = j + 1;
  }
  tail = 1;
  T.build();
  top1 = top2 = 0;
  for (head = 1; head <= n; head++) {
    mp[a[head]]++;
    while (mp[a[head]] > 1 || b[tail] != b[head]) {
      T.delet(tail);
      mp[a[tail]]--;
      tail++;
    }
    while (top1 > 0 && a[head] <= a[stk1[top1]]) {
      T.updatemin(stk1[top1 - 1] + 1, stk1[top1],
                  (a[head] - a[stk1[top1]]) / d);
      top1--;
    }
    stk1[++top1] = head;
    while (top2 > 0 && a[head] >= a[stk2[top2]]) {
      T.updatemax(stk2[top2 - 1] + 1, stk2[top2],
                  (a[head] - a[stk2[top2]]) / d);
      top2--;
    }
    stk2[++top2] = head;
    long long l = T.quer(head + k);
    if (l >= tail && head - l + 1 > ans) {
      ans = head - l + 1;
      ansl = l;
      ansr = head;
    }
  }
  printf("%d %d\n", ansl, ansr);
  return 0;
}
