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 maxn = 200005;
int n, K, D, ans1, ans2, sum, a[maxn], q1[maxn], q2[maxn];
map<int, int> b;
struct Tree {
  int s[maxn << 2], flg[maxn << 2];
  void Pushup(int d) { s[d] = min(s[d << 1], s[d << 1 | 1]); }
  void Mark(int d, int x) {
    s[d] += x;
    flg[d] += x;
  }
  void Pushdown(int d) {
    if (!flg[d]) return;
    Mark(d << 1, flg[d]);
    Mark(d << 1 | 1, flg[d]);
    flg[d] = 0;
  }
  void Build(int L, int R, int d) {
    if (L == R) {
      s[d] = -L;
      return;
    }
    int mid = (R - L >> 1) + L;
    Build(L, mid, d << 1);
    Build(mid + 1, R, d << 1 | 1);
    Pushup(d);
  }
  void Insert(int L, int R, int d, int x, int y, int p) {
    if (x <= L && R <= y) {
      Mark(d, p);
      return;
    }
    Pushdown(d);
    int mid = (R - L >> 1) + L;
    if (x <= mid) Insert(L, mid, d << 1, x, y, p);
    if (y > mid) Insert(mid + 1, R, d << 1 | 1, x, y, p);
    Pushup(d);
  }
  void Num(int L, int R, int d, int k) {
    if (L == R) {
      sum = L;
      return;
    }
    Pushdown(d);
    int mid = (R - L >> 1) + L;
    if (s[d << 1 | 1] <= k)
      Num(mid + 1, R, d << 1 | 1, k);
    else
      Num(L, mid, d << 1, k);
  }
  void Query(int L, int R, int d, int x, int y, int k) {
    if (sum) return;
    if (x <= L && R <= y) {
      if (s[d] <= k) Num(L, R, d, k);
      return;
    }
    Pushdown(d);
    int mid = (R - L >> 1) + L;
    if (y > mid) Query(mid + 1, R, d << 1 | 1, x, y, k);
    if (x <= mid) Query(L, mid, d << 1, x, y, k);
  }
} tr;
inline char nc() {
  static char buf[100000], *l, *r;
  if (l == r) r = (l = buf) + fread(buf, 1, 100000, stdin);
  if (l == r) return EOF;
  return *l++;
}
inline int Read() {
  int res = 0, f = 1;
  char ch = nc(), cc = ch;
  while (ch < '0' || ch > '9') cc = ch, ch = nc();
  if (cc == '-') f = -1;
  while (ch >= '0' && ch <= '9') res = res * 10 + ch - 48, ch = nc();
  return res * f;
}
void Solve(int L, int R) {
  if (L == R) return;
  b.clear();
  for (int i = L; i <= R; i++) a[i] = (a[i] + 1e9) / D + 1;
  int hed1 = 0, hed2 = 0;
  q1[0] = q2[0] = R + 1;
  int r = R + 1;
  for (int i = R; i >= L; i--) {
    if (b.count(a[i])) r = min(r, b[a[i]]);
    while (hed1 && a[i] > a[q1[hed1]])
      tr.Insert(1, n, 1, q1[hed1], q1[hed1 - 1] - 1, -a[q1[hed1]]), hed1--;
    tr.Insert(1, n, 1, i, q1[hed1] - 1, a[i]);
    q1[++hed1] = i;
    while (hed2 && a[i] < a[q2[hed2]])
      tr.Insert(1, n, 1, q2[hed2], q2[hed2 - 1] - 1, a[q2[hed2]]), hed2--;
    tr.Insert(1, n, 1, i, q2[hed2] - 1, -a[i]);
    q2[++hed2] = i;
    sum = 0;
    tr.Query(1, n, 1, i, r - 1, K - i);
    if (sum - i > ans2 - ans1 || (sum - i == ans2 - ans1 && i < ans1))
      ans1 = i, ans2 = sum;
    b[a[i]] = i;
  }
}
void Work() {
  for (int i = 1, j; i <= n; i = j + 1) {
    j = i;
    while (j < n && a[i] == a[j + 1]) j++;
    if (j - i > ans2 - ans1 || (j - i == ans2 - ans1 && i < ans1))
      ans1 = i, ans2 = j;
  }
  printf("%d %d", ans1, ans2);
}
int main() {
  n = Read();
  K = Read();
  D = Read();
  sum = 0;
  ans1 = ans2 = 1;
  for (int i = 1; i <= n; i++) a[i] = Read();
  if (D == 0) {
    Work();
    return 0;
  }
  tr.Build(1, n, 1);
  for (int i = 1, j; i <= n; i = j + 1) {
    j = i;
    while (j < n && ((a[j] % D) + D) % D == ((a[j + 1] % D) + D) % D) j++;
    Solve(i, j);
  }
  printf("%d %d", ans1, ans2);
  return 0;
}
