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 N = 2e5 + 10, inf = 3e9;
long long a[N], l1[N], mx[N], seg[4 * N], lazy[4 * N], k, lm;
set<long long> st;
bool fl;
deque<long long> dq1, dq2;
void shift(int v) {
  lazy[2 * v] += lazy[v];
  lazy[2 * v + 1] += lazy[v];
  seg[2 * v] += lazy[v];
  seg[2 * v + 1] += lazy[v];
  lazy[v] = 0;
}
void add(int s, int e, int l, int r, long long val, int v) {
  if (s >= r or e <= l) return;
  if (l <= s and e <= r) {
    seg[v] += val;
    lazy[v] += val;
    return;
  }
  shift(v);
  int mid = (s + e) / 2;
  add(s, mid, l, r, val, 2 * v);
  add(mid, e, l, r, val, 2 * v + 1);
  seg[v] = min(seg[2 * v], seg[2 * v + 1]);
}
void get(int s, int e, int l, int r, int v) {
  if (s >= r or e <= l or fl) return;
  shift(v);
  int mid = (s + e) / 2;
  if (l <= s and e <= r) {
    if (seg[v] <= k and e - s <= 1) {
      fl = true;
      lm = s;
      return;
    }
    if (seg[2 * v] <= k) {
      get(s, mid, l, r, 2 * v);
    } else {
      if (seg[2 * v + 1] <= k) get(mid, e, l, r, 2 * v + 1);
    }
    return;
  }
  get(s, mid, l, r, 2 * v);
  get(mid, e, l, r, 2 * v + 1);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, d;
  cin >> n >> k >> d;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] += (1e9);
  }
  if (d == 0) {
    int ans = 0, f1 = 0, la = 0;
    for (int i = 0; i < n; i++) {
      int j = i;
      while (i < n - 1 and a[i] == a[i + 1]) i++;
      if (i - j + 1 > ans) {
        ans = i - j + 1;
        f1 = j;
        la = i;
      }
    }
    cout << f1 + 1 << " " << la + 1 << endl;
    return 0;
  }
  long long ptr = 0;
  st.insert(a[0]);
  l1[0] = 0;
  mx[0] = 0;
  for (int i = 1; i < n; i++) {
    mx[i] = i;
    if ((a[i] % d) == (a[i - 1] % d)) mx[i] = mx[i - 1];
    if (st.find(a[i]) != st.end()) {
      while (a[ptr] != a[i]) st.erase(a[ptr++]);
      ptr++;
    } else {
      st.insert(a[i]);
    }
    l1[i] = max(mx[i], ptr);
  }
  for (int i = 0; i < n; i++) a[i] /= d;
  dq1.push_back(0);
  dq2.push_back(0);
  int lans = 0, rans = 0, ans = 1;
  for (int i = 1; i < n; i++) {
    while (dq1.size() and a[i] < a[dq1.back()]) {
      int f = 0;
      if (dq1.size() > 1) f = dq1[dq1.size() - 2] + 1;
      add(0, n, f, dq1.back() + 1, a[dq1.back()] - a[i], 1);
      dq1.pop_back();
    }
    dq1.push_back(i);
    while (dq2.size() and a[i] > a[dq2.back()]) {
      int f = 0;
      if (dq2.size() > 1) f = dq2[dq2.size() - 2] + 1;
      add(0, n, f, dq2.back() + 1, a[i] - a[dq2.back()], 1);
      dq2.pop_back();
    }
    dq2.push_back(i);
    add(0, n, 0, i, -1, 1);
    fl = false;
    get(0, n, l1[i], i + 1, 1);
    if (ans < i - lm + 1) {
      ans = i - lm + 1;
      lans = lm;
      rans = i;
    }
  }
  cout << lans + 1 << " " << rans + 1 << endl;
  return 0;
}
