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 N = 2e5 + 100, inF = 1e9 + 100;
int n, k, d, last, I, a[N], f[N], nxt[N];
int l, r = 1;
bool REV;
unordered_map<int, vector<int>> dex;
struct query {
  int dex, lim, l, r;
  query(int a, int b, int c, int d) { dex = a, lim = b, l = c, r = d; }
};
void check(int x, int y) {
  if (REV) {
    x = I - 1 - (x - last);
    y = I - 1 - (y - last);
    swap(x, y);
    x++;
    y++;
  }
  if (y - x > r - l)
    l = x, r = y;
  else if (y - x == r - l && x < l)
    l = x, r = y;
}
void solve_0() {
  a[n] = inF;
  int last = 0;
  for (int i = 0; i <= n; i++)
    if (a[last] != a[i]) {
      check(last, i);
      last = i;
    }
  cout << l + 1 << ' ' << r;
  exit(0);
}
void solve(int s, int e) {
  if (e - s <= 1) return;
  bool debug = (s + 1 == 29 && e == 54);
  vector<query> vec;
  int mid = (s + e) >> 1;
  solve(s, mid);
  solve(mid + 1, e);
  int p_max = mid + 1, p_min = mid + 1, lim = inF;
  int mini = a[mid], maxi = a[mid];
  mini = a[mid];
  int min_dex = inF;
  for (int i = mid; i < e; i++) {
    min_dex = min(min_dex, nxt[i]);
    mini = min(mini, a[i]);
    if (min_dex <= i) {
      f[i] = -inF;
      lim = min(lim, i);
    } else
      f[i] = mini + (i - mid + 1);
  }
  mini = a[mid];
  for (int i = mid; i >= s; i--) {
    mini = min(mini, a[i]);
    maxi = max(maxi, a[i]);
    while (p_max < e && a[p_max] < maxi) p_max++;
    while (p_min < e && a[p_min] > mini) p_min++;
    lim = min(lim, nxt[i]);
    if (lim <= mid) break;
    if (maxi - mini + 1 - (min(p_min, min(lim, p_max)) - i) <= k)
      check(i, min(p_min, min(lim, p_max)));
    vec.push_back(
        query(i, maxi + 1 - k - (mid - i), min(p_min, e), min(p_max, lim)));
  }
  vector<int> help;
  help.resize(e - mid);
  iota(help.begin(), help.end(), mid);
  sort(help.begin(), help.end(), [](int x, int y) { return f[x] > f[y]; });
  sort(vec.begin(), vec.end(), [](query a, query b) { return a.lim > b.lim; });
  set<int> st;
  int p = 0;
  for (int dex : help) {
    while (p < vec.size() && vec[p].lim > f[dex]) {
      if (st.size() && *st.begin() < vec[p].r &&
          *(--st.lower_bound(vec[p].r)) >= vec[p].l && vec[p].l < vec[p].r)
        check(vec[p].dex, *(--st.lower_bound(vec[p].r)) + 1);
      p++;
    }
    st.insert(dex);
  }
  while (p < vec.size()) {
    if (st.size() && *st.begin() < vec[p].r &&
        *(--st.lower_bound(vec[p].r)) >= vec[p].l && vec[p].l < vec[p].r)
      check(vec[p].dex, *(--st.lower_bound(vec[p].r)) + 1);
    p++;
  }
}
void SOLVE(int l, int r) {
  fill(nxt + l, nxt + r, inF);
  dex.clear();
  for (int i = l; i < r; i++) dex[a[i]].push_back(i);
  for (auto p : dex)
    for (int i = 1; i < p.second.size(); i++)
      nxt[p.second[i - 1]] = p.second[i];
  solve(l, r);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k >> d;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] += inF;
  }
  if (d == 0) solve_0();
  last = 0;
  for (int i = 0; i <= n; i++)
    if (a[last] % d != a[i] % d || i == n) {
      for (int j = last; j < i; j++)
        if (a[j] >= 0) a[j] /= d;
      I = i;
      SOLVE(last, i);
      reverse(a + last, a + i);
      REV = true;
      SOLVE(last, i);
      REV = false;
      reverse(a + last, a + i);
      last = i;
    }
  cout << ++l << ' ' << r;
  return 0;
}
