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;
typedef int Arr[200005];
int n, K, d, L, R, aim, anl, anr, gl, gr, hl, hr;
Arr a, b, g, h, pre;
struct Info {
  int mn, add, cov;
} t[1200005];
map<int, int> Maps;
inline int IN() {
  register int x = 0;
  char c;
  for (; (c = getchar()) < 48 && c ^ '-' || c > 57;)
    ;
  bool f = c == '-';
  if (f) (c = getchar());
  for (; c > 47 && c < 58; (c = getchar())) x = x * 10 + c - 48;
  return f ? -x : x;
}
inline bool dif(int x, int y) { return abs(x - y) % d != 0; }
inline void Mdy(int u, int xx, int op) {
  if (op == 0) {
    t[u].mn += xx;
    t[u].add += xx;
  } else {
    t[u].mn = 1e9;
    t[u].cov = 1;
    t[u].add = 0;
  }
}
inline void Dn(int u, int ll, int rr) {
  int mm = ll + rr >> 1;
  if (t[u].add) {
    Mdy(u << 1, t[u].add, 0);
    if (mm < rr) Mdy(u << 1 | 1, t[u].add, 0);
    t[u].add = 0;
  }
  if (t[u].cov) {
    Mdy(u << 1, 1, 1);
    if (mm < rr) Mdy(u << 1 | 1, 1, 1);
    t[u].cov = 0;
  }
}
void jia(int u, int ll, int rr) {
  if (L <= ll && rr <= R) {
    Mdy(u, aim, 0);
    return;
  }
  Dn(u, ll, rr);
  int mm = ll + rr >> 1;
  if (L <= mm) jia(u << 1, ll, mm);
  if (R > mm) jia(u << 1 | 1, mm + 1, rr);
  if (mm == rr)
    t[u].mn = t[u << 1].mn;
  else
    t[u].mn = min(t[u << 1].mn, t[u << 1 | 1].mn);
}
void gai(int u, int ll, int rr) {
  if (L <= ll && rr <= R) {
    Mdy(u, 1, 1);
    return;
  }
  Dn(u, ll, rr);
  int mm = ll + rr >> 1;
  if (L <= mm) gai(u << 1, ll, mm);
  if (R > mm) gai(u << 1 | 1, mm + 1, rr);
  if (mm == rr)
    t[u].mn = t[u << 1].mn;
  else
    t[u].mn = min(t[u << 1].mn, t[u << 1 | 1].mn);
}
int Qs(int u, int ll, int rr) {
  if (ll == rr) return ll;
  Dn(u, ll, rr);
  int mm = ll + rr >> 1;
  if (t[u << 1].mn <= K)
    return Qs(u << 1, ll, mm);
  else
    return Qs(u << 1 | 1, mm + 1, rr);
}
inline void Cov(int ll, int rr) {
  if (ll > rr) return;
  L = ll;
  R = rr;
  gai(1, 1, n);
}
inline void reset(int i) {
  g[gl = gr = 1] = h[hl = hr = 1] = i - 1;
  g[++gr] = i;
  h[++hr] = i;
  b[i] = a[i] / d + 1;
  if (i > 1) Cov(1, i - 1);
}
inline void Add(int ll, int rr, int x) {
  if (ll > rr) return;
  L = ll;
  R = rr;
  aim = x;
  jia(1, 1, n);
}
inline void upd(int x) {
  int _ = Qs(1, 1, n);
  if (x - _ > anr - anl) anl = _, anr = x;
}
inline void gao() {
  for (int i = 1, _r = n; i <= _r; ++i) pre[i] = 1;
  for (int i = 2, _r = n; i <= _r; ++i)
    pre[i] += (a[i] == a[i - 1]) * pre[i - 1];
  for (int i = 2, _r = n; i <= _r; ++i)
    if (pre[i] > anr - anl + 1) anr = i, anl = i - pre[i] + 1;
  printf("%d %d\n", anl, anr);
  exit(0);
}
int main() {
  n = IN();
  K = IN();
  d = IN();
  for (int i = 1, _r = n; i <= _r; ++i) {
    a[i] = IN() + (1e9);
    int &x = Maps[a[i]];
    pre[i] = x;
    x = i;
  }
  anl = anr = 1;
  if (d == 0) gao();
  for (int i = 1, _r = n; i <= _r; ++i)
    if (i == 1 || dif(a[i - 1], a[i]))
      reset(i);
    else {
      b[i] = a[i] / d + 1;
      if (pre[i]) Cov(1, pre[i]);
      if (pre[i] > g[gl]) {
        for (; gl <= gr && pre[i] >= g[gl]; ++gl)
          ;
        g[--gl] = pre[i];
      }
      if (pre[i] > h[hl]) {
        for (; hl <= hr && pre[i] >= h[hl]; ++hl)
          ;
        h[--hl] = pre[i];
      }
      if (pre[i] == i - 1) {
        g[++gr] = i;
        h[++hr] = i;
        continue;
      }
      if (b[i] > b[i - 1]) {
        for (; gr > gl && b[g[gr]] < b[i]; --gr)
          Add(g[gr - 1] + 1, g[gr], b[i] - b[g[gr]] - 1);
        Add(g[gl] + 1, g[gr], -1);
        g[++gr] = i;
        h[++hr] = i;
      } else {
        for (; hr > hl && b[h[hr]] > b[i]; --hr)
          Add(h[hr - 1] + 1, h[hr], b[h[hr]] - b[i] - 1);
        Add(h[hl] + 1, h[hr], -1);
        h[++hr] = i;
        g[++gr] = i;
      }
      upd(i);
    }
  printf("%d %d\n", anl, anr);
}
