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 n, k, d;
int a[200010], pre[200010];
map<int, int> vis;
int stackmax[200010], stackmin[200010], topmax = 0, topmin = 0;
struct node {
  int l;
  int r;
  long long minn;
  long long add;
} tree[800010];
void build(int now, int l, int r) {
  tree[now].l = l;
  tree[now].r = r;
  tree[now].minn = 2e9;
  tree[now].add = 0;
  if (l == r) return;
  int mid = (l + r) / 2;
  build(now * 2, l, mid);
  build(now * 2 + 1, mid + 1, r);
}
void add(int now, int x, int y, int ad) {
  int l = tree[now].l;
  int r = tree[now].r;
  if (l == x && r == y) {
    tree[now].add += ad;
    tree[now].minn += ad;
    return;
  }
  int mid = (l + r) / 2;
  if (tree[now].add) {
    add(now * 2, l, mid, tree[now].add);
    add(now * 2 + 1, mid + 1, r, tree[now].add);
    tree[now].add = 0;
  }
  if (y <= mid) {
    add(now * 2, x, y, ad);
  } else if (x > mid) {
    add(now * 2 + 1, x, y, ad);
  } else {
    add(now * 2, x, mid, ad);
    add(now * 2 + 1, mid + 1, y, ad);
  }
  tree[now].minn = min(tree[now * 2].minn, tree[now * 2 + 1].minn);
}
int check(int now, int x) {
  int l = tree[now].l;
  int r = tree[now].r;
  if (l == r) return l;
  int lson = now * 2;
  int rson = now * 2 + 1;
  int mid = (l + r) / 2;
  if (tree[now].add) {
    add(lson, l, mid, tree[now].add);
    add(rson, mid + 1, r, tree[now].add);
    tree[now].add = 0;
  }
  if (tree[lson].minn <= x)
    return check(lson, x);
  else
    return check(rson, x);
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  if (d == 0) {
    int maxn = 0, now = 0, l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
      if (a[i] != a[i - 1]) now = i;
      if (i - now + 1 > maxn) {
        maxn = i - now + 1;
        l = now;
        r = i;
      }
    }
    printf("%d %d\n", l, r);
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    pre[i] = vis[a[i]];
    vis[a[i]] = i;
  }
  int pr = 1;
  int maxn = 0, l = 0, r = 0;
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    while (pr <= pre[i] || (a[pr] % d + d) % d != (a[i] % d + d) % d) {
      add(1, pr, pr, 2e9 + 1);
      pr++;
    }
    add(1, i, i, -2e9 + i);
    while (topmax > 0 && a[stackmax[topmax]] < a[i]) {
      add(1, stackmax[topmax - 1] + 1, stackmax[topmax],
          a[i] / d - a[stackmax[topmax]] / d);
      topmax--;
    }
    stackmax[++topmax] = i;
    while (topmin > 0 && a[stackmin[topmin]] > a[i]) {
      add(1, stackmin[topmin - 1] + 1, stackmin[topmin],
          a[stackmin[topmin]] / d - a[i] / d);
      topmin--;
    }
    stackmin[++topmin] = i;
    int nowl = check(1, i + k);
    if (nowl >= pr && i - nowl + 1 > maxn) {
      maxn = i - nowl + 1;
      l = nowl;
      r = i;
    }
  }
  printf("%d %d\n", l, r);
  return 0;
}
