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;
struct node {
  int l, r;
  long long laz = 0, mn = 1e15;
};
const int MAXN = 2e5 + 200;
long long k, d, M = -1, nxtb[MAXN], nxtl[MAXN], al, alen, n;
vector<int> cur, en[MAXN];
multiset<int> ens;
node vs[MAXN * 4];
void vcnxt() {
  vector<pair<int, int> > hp;
  fill_n(nxtb, cur.size(), -1);
  for (int i = 0; i < cur.size(); i++) {
    while (!hp.empty() && hp.back().first <= cur[i])
      nxtb[hp.back().second] = i, hp.pop_back();
    hp.push_back({cur[i], i});
  }
  for (int i = 0; i < cur.size(); i++)
    if (nxtb[i] == -1) nxtb[i] = cur.size();
}
void prepnxt() {
  vcnxt();
  for (int j = 0; j < cur.size(); j++) swap(nxtb[j], nxtl[j]);
  for (int i = 0; i < cur.size(); i++) cur[i] *= -1;
  vcnxt();
  for (int j = 0; j < cur.size(); j++) swap(nxtb[j], nxtl[j]);
  for (int i = 0; i < cur.size(); i++) cur[i] *= -1;
}
void merge(int v) {
  vs[v].mn = min(vs[2 * v].mn, vs[2 * v + 1].mn);
  vs[v].mn += vs[v].laz;
}
void make(int v, int l, int r) {
  vs[v].l = l, vs[v].r = r;
  if (r - l == 1) {
    vs[v].mn = -l;
    return;
  }
  int mid = (l + r) / 2;
  make(2 * v, l, mid);
  make(2 * v + 1, mid, r);
  merge(v);
}
void add(int v, int ql, int qr, long long val) {
  if (qr <= vs[v].l || vs[v].r <= ql) return;
  if (ql <= vs[v].l && vs[v].r <= qr) {
    vs[v].laz += val;
    vs[v].mn += val;
    return;
  }
  add(2 * v, ql, qr, val);
  add(2 * v + 1, ql, qr, val);
  merge(v);
}
void chgbzmx(int la, int ra) {
  for (int i = la; i < ra;) {
    int l = i, r = nxtb[i];
    add(1, l, r, cur[i]);
    i = r;
  }
}
void chgbzmn(int la, int ra) {
  for (int i = la; i < ra;) {
    int l = i, r = nxtl[i];
    add(1, l, r, -cur[i]);
    i = r;
  }
}
int getind(int v, int ql, int qr, long long val, long long H) {
  if (qr <= vs[v].l || vs[v].r <= ql) return -1;
  H += vs[v].laz;
  if (ql <= vs[v].l && vs[v].r <= qr) {
    if (vs[v].mn + H - vs[v].laz > val) return -1;
    if (vs[v].r - vs[v].l == 1) return vs[v].l;
    if (vs[2 * v + 1].mn + H <= val) return getind(2 * v + 1, ql, qr, val, H);
    return getind(2 * v, ql, qr, val, H);
  }
  int r = getind(2 * v + 1, ql, qr, val, H);
  if (r == -1) return getind(2 * v, ql, qr, val, H);
  return r;
}
void preptek() {
  map<int, int> ls;
  for (int i = 0; i < cur.size(); i++) {
    en[i].clear();
    if (ls.find(cur[i]) != ls.end()) {
      en[ls[cur[i]]].push_back(i);
      ens.insert(i);
    }
    ls[cur[i]] = i;
  }
}
pair<int, int> solve() {
  int li, len = 0;
  prepnxt();
  preptek();
  make(1, 0, cur.size());
  chgbzmx(0, cur.size());
  chgbzmn(0, cur.size());
  for (int i = 0; i < cur.size(); i++) {
    int A = cur.size();
    if (!ens.empty()) A = *ens.begin();
    int res = getind(1, i, A, k - i, 0);
    if (res != -1 && res - i + 1 > len) li = i, len = res - i + 1;
    add(1, i, nxtb[i], -cur[i]);
    add(1, i, nxtl[i], cur[i]);
    chgbzmx(i + 1, nxtb[i]);
    chgbzmn(i + 1, nxtl[i]);
    for (int j = 0; j < en[i].size(); j++) ens.erase(ens.find(en[i][j]));
  }
  return {li, len};
}
int main() {
  cin >> n >> k >> d;
  int ans0 = 0, l0 = 0;
  vector<int> h0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (d != 0) {
      if (M == -1 || d == 0 || M == ((a % d) + d) % d) {
        if (a > 0 || a % d == 0)
          cur.push_back(a / d);
        else
          cur.push_back(a / d - 1);
        M = ((a % d) + d) % d;
      } else {
        pair<int, int> res = solve();
        if (alen < res.second)
          alen = res.second, al = res.first + i - cur.size();
        M = ((a % d) + d) % d;
        cur.clear();
        if (a > 0 || a % d == 0)
          cur.push_back(a / d);
        else
          cur.push_back(a / d - 1);
      }
    } else {
      if (h0.empty() || h0.back() == a)
        h0.push_back(a);
      else {
        if (ans0 < h0.size()) ans0 = h0.size(), l0 = i - h0.size();
        h0.clear();
        h0.push_back(a);
      }
    }
  }
  if (d != 0) {
    pair<int, int> res = solve();
    if (alen < res.second) alen = res.second, al = res.first + n - cur.size();
  }
  if (ans0 < h0.size()) ans0 = h0.size(), l0 = n - h0.size();
  if (d == 0)
    cout << l0 + 1 << ' ' << l0 + ans0;
  else
    cout << al + 1 << ' ' << al + alen;
}
