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 = 2e5 + 5;
int n, k, ans, ansl, ansr = -1, b[N], A[N], mi[N << 2], add[N << 2], len,
                     hsh[N];
long long d, a[N], c[N];
long long read() {
  long long x = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * w;
}
void build(int x, int l, int r) {
  add[x] = mi[x] = 0;
  if (l == r) return;
  int mid = l + r >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
}
void pushup(int x) { mi[x] = min(mi[x << 1], mi[x << 1 | 1]); }
void pushdown(int x) {
  if (!add[x]) return;
  add[x << 1] += add[x], add[x << 1 | 1] += add[x];
  mi[x << 1] += add[x], mi[x << 1 | 1] += add[x];
  add[x] = 0;
}
void insert(int x, int L, int R, int l, int r, int k) {
  if (l <= L && R <= r) {
    add[x] += k, mi[x] += k;
    return;
  }
  pushdown(x);
  int mid = L + R >> 1;
  if (l <= mid) insert(x << 1, L, mid, l, r, k);
  if (r > mid) insert(x << 1 | 1, mid + 1, R, l, r, k);
  pushup(x);
}
int query(int x, int L, int R, int k) {
  if (mi[x] > k) return 0;
  if (L == R) return L;
  pushdown(x);
  int mid = L + R >> 1;
  return mi[x << 1] <= k ? query(x << 1, L, mid, k)
                         : query(x << 1 | 1, mid + 1, R, k);
}
void find(int x, int L, int R, int l, int r, int k) {
  if (l <= L && R <= r) {
    if (!ans) ans = query(x, L, R, k);
    return;
  }
  int mid = R + L >> 1;
  pushdown(x);
  if (l <= mid) find(x << 1, L, mid, l, r, k);
  if (r > mid) find(x << 1 | 1, mid + 1, R, l, r, k);
}
int s1[N], s2[N], top1, top2;
void work(int left) {
  s1[top1 = 1] = s2[top2 = 1] = 0;
  build(1, 1, len);
  for (int i = 1, lst = 1; i <= len; i++) {
    for (; top1 > 1 && A[s1[top1]] <= A[i]; top1--)
      insert(1, 1, len, s1[top1 - 1] + 1, s1[top1], A[i] - A[s1[top1]]);
    s1[++top1] = i;
    for (; top2 > 1 && A[s2[top2]] >= A[i]; top2--)
      insert(1, 1, len, s2[top2 - 1] + 1, s2[top2], A[s2[top2]] - A[i]);
    s2[++top2] = i;
    insert(1, 1, len, i, i, i);
    int L = lst = max(lst, hsh[b[i + left - 1]] + 1), R = i;
    hsh[b[i + left - 1]] = i;
    ans = 0;
    find(1, 1, len, L, R, i + k);
    if (ansr - ansl < i - ans) ansl = left + ans - 1, ansr = left + i - 1;
  }
  for (int i = 1; i <= len; i++) hsh[b[i + left - 1]] = 0;
}
int main() {
  scanf("%d%d%lld", &n, &k, &d);
  for (int i = 1; i <= n; i++) c[i] = a[i] = read();
  sort(c + 1, c + 1 + n);
  len = unique(c + 1, c + 1 + n) - c - 1;
  for (int i = 1; i <= n; i++) b[i] = lower_bound(c + 1, c + 1 + len, a[i]) - c;
  if (d == 0) {
    int now = 1;
    ansr = ansl = 1;
    for (int i = 2; i <= n + 1; i++)
      if (a[i] == a[i - 1])
        now++;
      else if (now > ansr - ansl + 1)
        ansr = i - 1, ansl = i - now, now = 1;
      else
        now = 1;
    printf("%d %d\n", ansl, ansr);
    return 0;
  } else {
    for (int l = 1, r; l <= n; l = r) {
      for (r = l + 1; r <= n && (a[l] % d + d) % d == (a[r] % d + d) % d; r++)
        ;
      len = 0;
      for (int i = l; i < r; i++) A[++len] = a[i] / d;
      work(l);
    }
  }
  printf("%d %d\n", ansl, ansr);
}
