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;
int _max(int x, int y) { return x > y ? x : y; }
int _min(int x, int y) { return x < y ? x : y; }
const int N = 200001;
int read() {
  int s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * f;
}
void put(int x) {
  if (x >= 10) put(x / 10);
  putchar(x % 10 + '0');
}
struct tnode {
  int lc, rc, l, r, c, lazy;
} t[N * 2];
int cnt;
int tp1, sta1[N], tp2, sta2[N];
int n, k, d, a[N], pre[N];
map<int, int> mp;
int ans, L, R;
void bt(int l, int r) {
  int now = ++cnt;
  t[now].l = l, t[now].r = r;
  t[now].lc = t[now].rc = -1;
  t[now].c = l - k;
  t[now].lazy = 0;
  if (l == r)
    t[now].c = -l - k;
  else {
    int mid = (l + r) / 2;
    t[now].lc = cnt + 1;
    bt(l, mid);
    t[now].rc = cnt + 1;
    bt(mid + 1, r);
    t[now].c = _min(t[t[now].lc].c, t[t[now].rc].c);
  }
}
void pushdown(int now) {
  if (!t[now].lazy) return;
  int lc = t[now].lc, rc = t[now].rc;
  t[lc].c += t[now].lazy, t[rc].c += t[now].lazy;
  t[lc].lazy += t[now].lazy, t[rc].lazy += t[now].lazy;
  t[now].lazy = 0;
}
void update(int now) {
  int lc = t[now].lc, rc = t[now].rc;
  t[now].c = _min(t[lc].c, t[rc].c);
}
void change(int now, int l, int r, int c) {
  if (t[now].l == l && t[now].r == r) {
    t[now].c += c, t[now].lazy += c;
    return;
  }
  pushdown(now);
  int mid = (t[now].l + t[now].r) / 2;
  if (r <= mid)
    change(t[now].lc, l, r, c);
  else if (l > mid)
    change(t[now].rc, l, r, c);
  else
    change(t[now].lc, l, mid, c), change(t[now].rc, mid + 1, r, c);
  update(now);
}
int findr(int now, int l, int r) {
  if (t[now].c > 0) return -1;
  if (t[now].l == t[now].r) return t[now].l;
  pushdown(now);
  int mid = (t[now].l + t[now].r) / 2;
  if (r <= mid)
    return findr(t[now].lc, l, r);
  else if (l > mid)
    return findr(t[now].rc, l, r);
  else {
    int c = findr(t[now].rc, mid + 1, r);
    if (c != -1) return c;
    return findr(t[now].lc, l, mid);
  }
}
int findp(int now, int p) {
  if (t[now].l == t[now].r) return t[now].c;
  pushdown(now);
  int mid = (t[now].l + t[now].r) / 2;
  if (p <= mid)
    return findp(t[now].lc, p);
  else
    return findp(t[now].rc, p);
}
void solve(int l, int r) {
  cnt = 0;
  bt(1, r - l + 1);
  change(1, 1, r - l + 1, r - l + 1);
  sta1[0] = sta2[0] = r - l + 2;
  tp1 = tp2 = 0;
  int up = r - l + 1;
  for (int i = r - l + 1; i >= 1; i--) {
    a[i + l - 1] /= d;
    while (tp1 && a[i + l - 1] > a[sta1[tp1] + l - 1])
      change(1, sta1[tp1], sta1[tp1 - 1] - 1, -a[sta1[tp1] + l - 1]), --tp1;
    while (tp2 && a[i + l - 1] < a[sta2[tp2] + l - 1])
      change(1, sta2[tp2], sta2[tp2 - 1] - 1, a[sta2[tp2] + l - 1]), --tp2;
    change(1, i, sta1[tp1] - 1, a[i + l - 1]),
        change(1, i, sta2[tp2] - 1, -a[i + l - 1]);
    sta1[++tp1] = i, sta2[++tp2] = i;
    up = _min(up, pre[i + l - 1] - l);
    int hh = findp(1, 60);
    int z = findr(1, i, up);
    if (z >= i) {
      if (z - i + 1 > ans)
        ans = z - i + 1, L = i + l - 1, R = z + l - 1;
      else if (z - i + 1 == ans && i + l - 1 < L)
        L = i + l - 1, R = z + l - 1;
    }
    change(1, 1, r - l + 1, -1);
  }
}
int main() {
  n = read(), k = read(), d = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  if (d == 0) {
    int l = 1;
    ans = 0;
    for (int i = 2; i <= n; i++) {
      if (a[i] != a[i - 1]) {
        if (i - l > ans) ans = i - l, L = l, R = i - 1;
        l = i;
      }
    }
    if (n - l + 1 > ans) L = l, R = n;
    printf("%d %d\n", L, R);
    return 0;
  }
  int mn = a[1];
  for (int i = 2; i <= n; i++) mn = _min(mn, a[i]);
  for (int i = 1; i <= n; i++) a[i] -= mn;
  for (int i = n; i >= 1; i--)
    pre[i] = mp[a[i]] == 0 ? n + 1 : mp[a[i]], mp[a[i]] = i;
  int l = 1;
  ans = L = R = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] % d != a[i - 1] % d) solve(l, i - 1), l = i;
  }
  solve(l, n);
  printf("%d %d\n", L, R);
  return 0;
}
