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() {
  char c = getchar();
  int f = 1, t = 0;
  while (c > '9' || c < '0') f = (c == '-') ? -1 : 1, c = getchar();
  while (c >= '0' && c <= '9') t = t * 10 + c - '0', c = getchar();
  return t * f;
}
int n, ql, ansl, ansr, anslen;
int q1[200005], tp1, q2[200005], tp2, m, tot, id[200005];
int st[200005], rk[200005], buc[200005], pre[200005], ed;
long long K, D, a[200005], val[200005];
void upd(int l, int r) {
  if (r - l + 1 > anslen) anslen = r - l + 1, ansl = l, ansr = r;
}
struct Block {
  int ql, qr;
  long long mn, tag;
  void build(int ID) {
    mn = 0x3f3f3f3f3f3f3f3fLL;
    for (int i = ql; i <= qr; i++) val[i] = 0x3f3f3f3f3f3f3f3fLL, id[i] = ID;
  }
  void pushdown() {
    if (!tag) return;
    for (int i = ql; i <= qr; i++) val[i] += tag;
    tag = 0;
  }
  void modify(int L, int R, long long v) {
    if (L <= ql && R >= qr) return (void)(mn += v, tag += v);
    pushdown(), mn = 0x3f3f3f3f3f3f3f3fLL;
    for (int i = max(ql, L); i <= min(qr, R); i++) val[i] += v;
    for (int i = ql; i <= qr; i++) mn = min(mn, val[i]);
  }
  int query(int L, int R) {
    if ((L <= ql && R >= qr) && (mn > K * D)) return 0;
    pushdown();
    for (int i = max(L, ql); i <= min(R, qr); i++)
      if (val[i] <= K * D) return i;
    return 0;
  }
} T[505];
void modify(int L, int R, long long v) {
  int id1 = id[L], id2 = id[R];
  for (int i = id1; i <= id2; i++) T[i].modify(L, R, v);
}
int query(int L, int R) {
  int id1 = id[L], id2 = id[R];
  for (int i = id1; i <= id2; i++) {
    int ret = T[i].query(L, R);
    if (ret) return ret;
  }
  return 0;
}
void subtask1() {
  a[0] = a[n + 1] = 0x3f3f3f3f;
  for (int i = 1, j = 1; i <= n; j = (++i)) {
    while (a[j + 1] == a[i]) j++;
    upd(i, j);
  }
  printf("%d %d\n", ansl, ansr);
}
void subtask2() {
  for (int i = 1; i <= n; i++) st[i] = a[i];
  sort(st + 1, st + n + 1), ed = unique(st + 1, st + n + 1) - st - 1;
  for (int i = 1; i <= n; i++)
    rk[i] = lower_bound(st + 1, st + ed + 1, a[i]) - st;
  for (int i = 1; i <= n; i++) pre[i] = buc[rk[i]], buc[rk[i]] = i;
  ql = 1, anslen = ansl = ansr = 1, m = sqrt(n);
  for (tot = 1; (tot - 1) * m + 1 <= n; tot++)
    T[tot].ql = T[tot - 1].qr + 1, T[tot].qr = min(n, tot * m),
    T[tot].build(tot);
  q1[++tp1] = 1, q2[++tp2] = 1, T[1].modify(1, 1, -0x3f3f3f3f3f3f3f3fLL);
  for (int i = 2, lst; i <= n; i++) {
    ql = (abs(a[i] - a[i - 1]) % D == 0) ? max(pre[i] + 1, ql) : i;
    T[id[i]].modify(i, i, -0x3f3f3f3f3f3f3f3fLL), lst = q1[tp1];
    while (tp1 && a[i] < a[q1[tp1]])
      modify(q1[tp1 - 1] + 1, lst, a[q1[tp1]] - a[i]), lst = q1[--tp1];
    q1[++tp1] = i, lst = q2[tp2];
    while (tp2 && a[i] > a[q2[tp2]])
      modify(q2[tp2 - 1] + 1, lst, a[i] - a[q2[tp2]]), lst = q2[--tp2];
    q2[++tp2] = i, modify(1, i - 1, -D), upd(query(ql, i), i);
  }
  printf("%d %d\n", ansl, ansr);
}
int main() {
  n = read(), K = read(), D = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  if (!D)
    subtask1();
  else
    subtask2();
}
