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 read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch - '0' < 0 || ch - +'0' > 9) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch - '0' >= 0 && ch - '0' <= 9) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, K, D;
int a[200010], L[200010];
map<int, int> ma;
struct Segment_Tree {
  long long t[200010 * 4], tag[200010 * 4];
  void update(int k) { t[k] = min(t[k * 2], t[k * 2 + 1]); }
  void pushdown(int k) {
    if (!tag[k]) return;
    t[k * 2] += tag[k];
    tag[k * 2] += tag[k];
    t[k * 2 + 1] += tag[k];
    tag[k * 2 + 1] += tag[k];
    tag[k] = 0;
  }
  void build(int k, int l, int r) {
    if (l == r) return t[k] = 1ll * l * D, void();
    int mid = (l + r) / 2;
    build(k * 2, l, mid);
    build(k * 2 + 1, mid + 1, r);
    update(k);
  }
  void modi(int k, int l, int r, int x, int y, int z) {
    if (l >= x && r <= y) return t[k] += z, tag[k] += z, void();
    pushdown(k);
    int mid = (l + r) / 2;
    if (mid >= x) modi(k * 2, l, mid, x, y, z);
    if (mid < y) modi(k * 2 + 1, mid + 1, r, x, y, z);
    update(k);
  }
  int queryx(int k, int l, int r, long long x) {
    if (l == r) return l;
    pushdown(k);
    int mid = (l + r) / 2;
    if (t[k * 2] <= x) return queryx(k * 2, l, mid, x);
    return queryx(k * 2 + 1, mid + 1, r, x);
  }
  int query(int k, int l, int r, int x, int y, long long z) {
    if (l >= x && r <= y) {
      if (t[k] > z) return -1;
      return queryx(k, l, r, z);
    }
    pushdown(k);
    int mid = (l + r) / 2;
    if (mid >= x && mid >= y) return query(k * 2, l, mid, x, y, z);
    if (mid < y && mid < x) return query(k * 2 + 1, mid + 1, r, x, y, z);
    int res = query(k * 2, l, mid, x, y, z);
    if (res == -1) return query(k * 2 + 1, mid + 1, r, x, y, z);
    return res;
  }
} S;
int s1[200010], s2[200010], top1, top2;
int ansl, ansr = -1;
int main() {
  n = read();
  K = read();
  D = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  if (!D) {
    for (int i = 1; i <= n; i++) {
      int R = i;
      while (R < n && a[R + 1] == a[i]) R++;
      if (R - i + 1 > ansr - ansl + 1) ansl = i, ansr = R;
      i = R;
    }
    cout << ansl << " " << ansr << endl;
    return 0;
  }
  L[0] = 1;
  for (int i = 1; i <= n; i++) {
    L[i] = L[i - 1];
    while (ma[a[i]]) {
      ma[a[L[i]]] = 0;
      L[i]++;
    }
    ma[a[i]] = 1;
  }
  for (int i = 1; i <= n; i++) {
    int R = i;
    while (R < n && (a[R + 1] % D + D) % D == (a[i] % D + D) % D) R++;
    for (int j = i; j <= R; j++) L[j] = max(L[j], i);
    i = R;
  }
  S.build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    while (top1 && a[i] > a[s1[top1]]) {
      S.modi(1, 1, n, s1[top1 - 1] + 1, s1[top1], -a[s1[top1]]);
      top1--;
    }
    S.modi(1, 1, n, s1[top1] + 1, i, a[i]);
    s1[++top1] = i;
    while (top2 && a[i] < a[s2[top2]]) {
      S.modi(1, 1, n, s2[top2 - 1] + 1, s2[top2], a[s2[top2]]);
      top2--;
    }
    S.modi(1, 1, n, s2[top2] + 1, i, -a[i]);
    s2[++top2] = i;
    int x = S.query(1, 1, n, L[i], i, 1ll * (i + K) * D);
    if (x == -1) continue;
    if (i - x + 1 > ansr - ansl + 1 ||
        (i - x + 1 == ansr - ansl + 1 && x < ansl))
      ansl = x, ansr = i;
  }
  cout << ansl << " " << ansr << endl;
  return 0;
}
