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 long long inf = 10000000000000000LL;
map<int, int> M;
struct treenode {
  long long add, min;
};
treenode tree[2000000];
int g[300000], q1[300000], q2[300000], u[300000], v[300000];
int d, h, i, j, k, l, n, s1, s2, t, t1, t2;
inline void pushdown(int l, int r, int node) {
  tree[node].min = tree[node].min + tree[node].add;
  if (l != r) {
    tree[node << 1].add = tree[node << 1].add + tree[node].add;
    tree[node << 1 | 1].add = tree[node << 1 | 1].add + tree[node].add;
  }
  tree[node].add = 0;
  return;
}
inline void pushup(int l, int r, int node) {
  int mid = (l + r) >> 1;
  pushdown(l, mid, node << 1);
  pushdown(mid + 1, r, node << 1 | 1);
  tree[node].min = min(tree[node << 1].min, tree[node << 1 | 1].min);
  return;
}
inline void inserttree(int l, int r, int x, long long y, int node) {
  pushdown(l, r, node);
  if (l == r)
    tree[node].min = y;
  else {
    int mid = (l + r) >> 1;
    if (x <= mid)
      inserttree(l, mid, x, y, node << 1);
    else
      inserttree(mid + 1, r, x, y, node << 1 | 1);
    pushup(l, r, node);
  }
  return;
}
inline void addtree(int l, int r, int x, int y, int z, int node) {
  pushdown(l, r, node);
  if ((l == x) && (r == y))
    tree[node].add = tree[node].add + z;
  else {
    int mid = (l + r) >> 1;
    if (y <= mid)
      addtree(l, mid, x, y, z, node << 1);
    else if (x > mid)
      addtree(mid + 1, r, x, y, z, node << 1 | 1);
    else {
      addtree(l, mid, x, mid, z, node << 1);
      addtree(mid + 1, r, mid + 1, y, z, node << 1 | 1);
    }
    pushup(l, r, node);
  }
  return;
}
inline int asktree(int l, int r, int x, int node) {
  pushdown(l, r, node);
  if (l == r) return l;
  pushup(l, r, node);
  int mid = (l + r) >> 1;
  if (tree[node << 1].min <= x)
    return asktree(l, mid, x, node << 1);
  else
    return asktree(mid + 1, r, x, node << 1 | 1);
}
int main() {
  scanf("%d%d%d", &n, &h, &d);
  for (i = 1; i <= n; i++) scanf("%d", &g[i]);
  s1 = 1, s2 = 1;
  if (!d) {
    for (i = 1; i <= n; i = j) {
      for (j = i; (j <= n) && (g[i] == g[j]); j++)
        ;
      if (j - i > s2 - s1 + 1) s1 = i, s2 = j - 1;
    }
    printf("%d %d", s1, s2);
    return 0;
  }
  for (i = 1; i <= n; i++) {
    g[i] = g[i] + 1000000000;
    u[i] = g[i] / d, v[i] = g[i] % d;
  }
  for (i = 1; i <= n; i++) inserttree(1, n, i, inf, 1);
  for (i = 1; i <= n; i++) {
    j = k;
    if (M[g[i]]) k = max(k, M[g[i]]);
    M[g[i]] = i;
    if (v[i] != v[i - 1]) k = max(k, i - 1);
    for (l = j + 1; l <= k; l++) inserttree(1, n, l, inf, 1);
    inserttree(1, n, i, i, 1);
    for (; (t1 > 0) && (u[i] <= u[q1[t1]]); t1--)
      addtree(1, n, q1[t1 - 1] + 1, q1[t1], u[q1[t1]], 1);
    t1++, q1[t1] = i, addtree(1, n, q1[t1 - 1] + 1, q1[t1], -u[q1[t1]], 1);
    for (; (t2 > 0) && (u[i] >= u[q2[t2]]); t2--)
      addtree(1, n, q2[t2 - 1] + 1, q2[t2], -u[q2[t2]], 1);
    t2++, q2[t2] = i, addtree(1, n, q2[t2 - 1] + 1, q2[t2], u[q2[t2]], 1);
    t = asktree(1, n, i + h, 1);
    if (i - t + 1 > s2 - s1 + 1) s1 = t, s2 = i;
  }
  printf("%d %d\n", s1, s2);
  return 0;
}
