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 = 2 * 100000 + 10, INF = 0x3f3f3f3f;
struct seg_tree {
  int l, r, s, c;
} t[MAXN * 4];
int n, k, d, Tohka, L, a[MAXN], b[MAXN];
map<int, int> w;
bool FLAG;
void Upd(int first, int second) {
  if (first > Tohka) Tohka = first, L = second;
}
int f[MAXN], g[MAXN];
void Build(int first, int l, int r) {
  t[first].l = l, t[first].r = r;
  t[first].s = 0, t[first].c = 0;
  if (l == r) return;
  Build((first << 1), l, ((t[first].l + t[first].r) >> 1)),
      Build(((first << 1) | 1), ((t[first].l + t[first].r) >> 1) + 1, r);
}
void Upd(int first) {
  if (t[first].l != t[first].r)
    t[first].c = min(t[(first << 1)].c, t[((first << 1) | 1)].c);
}
void Clean(int first) {
  int u = t[first].s;
  if (!u) return;
  t[first].s = 0;
  t[first].c += u;
  if (t[first].l != t[first].r)
    t[(first << 1)].s += u, t[((first << 1) | 1)].s += u;
}
void Ins(int first, int l, int r, int d) {
  Clean(first);
  if (l > r) return;
  if (t[first].l == l && t[first].r == r) {
    t[first].s += d;
    Clean(first);
    return;
  }
  if (r <= ((t[first].l + t[first].r) >> 1))
    Ins((first << 1), l, r, d), Clean(((first << 1) | 1));
  else if (l > ((t[first].l + t[first].r) >> 1))
    Ins(((first << 1) | 1), l, r, d), Clean((first << 1));
  else
    Ins((first << 1), l, ((t[first].l + t[first].r) >> 1), d),
        Ins(((first << 1) | 1), ((t[first].l + t[first].r) >> 1) + 1, r, d);
  Upd(first);
}
int Query(int first, int l, int r, int K) {
  Clean(first);
  if (l > r) return -1;
  if (t[first].l == t[first].r)
    if (t[first].c <= K)
      return l;
    else
      return -1;
  int w = -1;
  if (r <= ((t[first].l + t[first].r) >> 1))
    w = Query((first << 1), l, r, K), Clean(((first << 1) | 1));
  else if (l > ((t[first].l + t[first].r) >> 1))
    w = Query(((first << 1) | 1), l, r, K), Clean((first << 1));
  else {
    Clean((first << 1));
    Clean(((first << 1) | 1));
    if (t[first].c > K)
      ;
    else {
      if (t[(first << 1)].c <= K)
        w = Query((first << 1), l, ((t[first].l + t[first].r) >> 1), K);
      if (w == -1)
        w = Query(((first << 1) | 1), ((t[first].l + t[first].r) >> 1) + 1, r,
                  K);
    }
  }
  Upd(first);
  return w;
}
void solve(int n, int Sp) {
  for (int i = 1; i <= n; ++i) b[i] /= d;
  Build(1, 1, n);
  w.clear();
  f[0] = g[0] = 0;
  for (int i = 1, p = 0; i <= n; ++i) {
    p = max(p, w[b[i]]);
    w[b[i]] = i;
    for (; f[0] && b[f[f[0]]] <= b[i]; --f[0])
      if (f[0] > 1) Ins(1, 1, f[f[0] - 1], -(b[f[f[0] - 1]] - b[f[f[0]]]));
    f[++f[0]] = i;
    if (f[0] != 1) Ins(1, 1, f[f[0] - 1], b[f[f[0] - 1]] - b[i]);
    for (; g[0] && b[g[g[0]]] >= b[i]; --g[0])
      if (g[0] > 1) Ins(1, 1, g[g[0] - 1], -(b[g[g[0]]] - b[g[g[0] - 1]]));
    g[++g[0]] = i;
    if (g[0] != 1) Ins(1, 1, g[g[0] - 1], b[i] - b[g[g[0] - 1]]);
    Ins(1, 1, i, -1);
    int ww = Query(1, p + 1, i, k - 1);
    if (ww != -1) Upd(i - ww + 1, Sp - 1 + ww);
  }
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] += (int)1e9;
  if (!d) {
    for (int i = 1, p = 0; i <= n; ++i) {
      if (i > 1 && a[i - 1] != a[i]) p = i - 1;
      Upd(i - p, p + 1);
    }
  } else
    for (int i = 1; i <= n;) {
      int t = (a[i]) % d, j = i + 1;
      for (; (a[j]) % d == t && j <= n; ++j)
        ;
      memcpy(b + 1, a + i, sizeof(int) * (j - i));
      if (j - i == 1)
        Upd(1, i);
      else
        solve(j - i, i);
      i = j;
    }
  cout << L << " " << L + Tohka - 1 << endl;
  fclose(stdin);
  fclose(stdout);
  return 0;
}
