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;
const int oo = 100000000;
int n, k, d, m, Nmax, Nmin, ans, pL, pR;
struct data {
  int mod, div, rk, id;
} s[maxN];
struct Tnode {
  int mstV[2], val, add;
} tree[4 * maxN];
int t[maxN], id[maxN];
bool vis[maxN];
bool Readln() {
  scanf("%d%d%d\n", &n, &k, &d);
  if (d == 0) {
    for (int i = 1; i <= n; i++) scanf("%d", &s[i].div);
    int st = 1;
    for (int i = 2; i <= n; i++) {
      if (s[i].div != s[i - 1].div) {
        if (i - st > ans) {
          ans = i - st;
          pL = st;
          pR = i - 1;
        }
        st = i;
      }
    }
    if (n - st + 1 > ans) {
      ans = n - st + 1;
      pL = st;
      pR = n;
    }
    printf("%d %d\n", pL, pR);
    return true;
  }
  for (int i = 1; i <= n; i++) {
    int val;
    scanf("%d", &val);
    s[i].mod = val % d;
    s[i].div = val / d;
    if (s[i].mod < 0) {
      s[i].mod += d;
      s[i].div--;
    }
    s[i].id = i;
  }
  return false;
}
void down(int root) {
  if (tree[root].add == 0) return;
  tree[root * 2].add += tree[root].add;
  tree[root * 2].val += tree[root].add;
  tree[root * 2 + 1].add += tree[root].add;
  tree[root * 2 + 1].val += tree[root].add;
  tree[root].add = 0;
}
int maxx(int a, int b) {
  if (a == 0) return b;
  if (b == 0) return a;
  if (t[a] > t[b])
    return a;
  else
    return b;
}
int minn(int a, int b) {
  if (a == 0) return b;
  if (b == 0) return a;
  if (t[a] < t[b])
    return a;
  else
    return b;
}
void updata(int root) {
  tree[root].val = min(tree[root * 2].val, tree[root * 2 + 1].val);
  tree[root].mstV[1] = maxx(tree[root * 2].mstV[1], tree[root * 2 + 1].mstV[1]);
  tree[root].mstV[0] = minn(tree[root * 2].mstV[0], tree[root * 2 + 1].mstV[0]);
}
void inserttree(int root, int lef, int rig, int p, int val) {
  if (rig < p || lef > p) return;
  if (lef == rig && rig == p) {
    tree[root].val = val;
    tree[root].mstV[1] = p;
    tree[root].mstV[0] = p;
    return;
  }
  down(root);
  int mid = (lef + rig) / 2;
  inserttree(root * 2, lef, mid, p, val);
  inserttree(root * 2 + 1, mid + 1, rig, p, val);
  updata(root);
}
int findtree(int root, int lef, int rig, int lo, int hi, int val, int flag) {
  if (rig < lo || hi < lef) return 0;
  if (lo <= lef && rig <= hi) {
    if (flag == 0)
      if (t[tree[root].mstV[flag]] > val) return rig;
    if (flag == 1)
      if (t[tree[root].mstV[flag]] < val) return rig;
  }
  if (lef == rig) return -1;
  down(root);
  int mid = (lef + rig) / 2;
  int ret = findtree(root * 2, lef, mid, lo, hi, val, flag);
  if (ret == 0) return findtree(root * 2 + 1, mid + 1, rig, lo, hi, val, flag);
  if (ret == mid)
    ret = max(ret, findtree(root * 2 + 1, mid + 1, rig, lo, hi, val, flag));
  return ret;
}
void addtree(int root, int lef, int rig, int lo, int hi, int val) {
  if (rig < lo || hi < lef) return;
  if (lo <= lef && rig <= hi) {
    tree[root].val += val;
    tree[root].add += val;
    return;
  }
  down(root);
  int mid = (lef + rig) / 2;
  addtree(root * 2, lef, mid, lo, hi, val);
  addtree(root * 2 + 1, mid + 1, rig, lo, hi, val);
  updata(root);
}
int asktree(int root, int lef, int rig, int lo, int hi) {
  if (hi < lef || rig < lo) return -1;
  if (lo <= lef && rig <= hi) {
    if (tree[root].val > k) return -1;
  }
  if (lef == rig) return lef;
  down(root);
  int mid = (lef + rig) / 2;
  int ret = asktree(root * 2 + 1, mid + 1, rig, lo, hi);
  if (ret != -1) return ret;
  return asktree(root * 2, lef, mid, lo, hi);
}
int getmost(int root, int lef, int rig, int lo, int hi, int flag) {
  if (rig < lo || hi < lef) return 0;
  if (lo <= lef && rig <= hi) return tree[root].mstV[flag];
  int mid = (lef + rig) / 2;
  int ret1 = getmost(root * 2, lef, mid, lo, hi, flag);
  int ret2 = getmost(root * 2 + 1, mid + 1, rig, lo, hi, flag);
  if (flag == 0)
    return minn(ret1, ret2);
  else
    return maxx(ret1, ret2);
}
void task(int flag, int i, int j) {
  int tmp = findtree(1, 1, m, i + 1, j, t[i], flag ^ 1);
  addtree(1, 1, m, tmp + 1, j, 1);
  int en = tmp;
  for (; en > i;) {
    int now = getmost(1, 1, m, i + 1, en, flag ^ 1);
    int val = t[now];
    addtree(1, 1, m, now, en, -(abs(val - t[i]) - 1));
    if (tree[1].val < 0) {
      int a = 1;
    }
    if (en >= j) {
      if (flag ^ 1 == 1)
        Nmax = val;
      else
        Nmin = val;
    }
    en = now - 1;
  }
}
void Clear(int q) {
  for (int i = 1; i <= q; i++) vis[id[i]] = false;
  for (int i = 1; i <= 4 * q; i++) {
    tree[i].val = oo;
    tree[i].mstV[1] = 0;
    tree[i].mstV[0] = 0;
    tree[i].add = 0;
  }
}
void work(int st) {
  int j = 0;
  for (int i = 1; i <= m; i++) {
    if (i == 2) {
      int a = 1;
    }
    if (j < i) {
      Nmax = -oo;
      Nmin = oo;
      j = i;
    }
    for (; j <= m; j++)
      if (!vis[id[j]]) {
        Nmax = max(Nmax, t[j]);
        Nmin = min(Nmin, t[j]);
        inserttree(1, 1, m, j, Nmax - Nmin + 1 - (j - i + 1));
        vis[id[j]] = true;
      } else
        break;
    int tmp = asktree(1, 1, m, i, j - 1);
    if (tmp - i + 1 > ans) {
      ans = tmp - i + 1;
      pL = st + i - 1;
      pR = st + tmp - 1;
    }
    inserttree(1, 1, m, i, oo);
    vis[id[i]] = false;
    if (i == j - 1) continue;
    if (t[i] < t[i + 1])
      task(1, i, j - 1);
    else
      task(0, i, j - 1);
  }
  Clear(m);
}
bool cmp1(data a, data b) { return a.div < b.div; }
bool cmp2(data a, data b) { return a.id < b.id; }
void Solve() {
  sort(s + 1, s + 1 + n, cmp1);
  int cal = 1;
  s[1].rk = 1;
  for (int i = 2; i <= n; i++) {
    if (s[i].div != s[i - 1].div) cal++;
    s[i].rk = cal;
  }
  sort(s + 1, s + 1 + n, cmp2);
  Clear(n);
  for (int i = 1; i <= n;) {
    m = 1;
    t[1] = s[i].div;
    id[1] = s[i].rk;
    int tmp = i;
    i++;
    for (; i <= n && s[i].mod == s[i - 1].mod; i++) {
      m++;
      t[m] = s[i].div;
      id[m] = s[i].rk;
    }
    if (tmp <= 71 && i > 71) {
      int a = 1;
    }
    work(tmp);
  }
  printf("%d %d\n", pL, pR);
}
int main() {
  if (!Readln()) Solve();
  return 0;
}
