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;
using ll = long long;
const int N = 2e5 + 2, mod = 1e9 + 7, inf = INT_MAX;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
stack<int> mn, mx;
pair<int, int> ans;
int n, k, d, lw = 1, best = 0, a[N];
unordered_map<int, int, custom_hash> pre;
struct segtree {
  ll lazy[N << 2], tree[N << 2];
  void push(int id, int l, int r) {
    tree[id] += lazy[id];
    if (l < r) {
      lazy[(id << 1)] += lazy[id];
      lazy[((id << 1) | 1)] += lazy[id];
    }
    lazy[id] = 0;
  }
  void update(int L, int R, ll V, int id = 1, int l = 1, int r = n) {
    push(id, l, r);
    if (l > R || r < L) {
      return;
    }
    if (L <= l && r <= R) {
      lazy[id] = V;
      push(id, l, r);
      return;
    }
    update(L, R, V, (id << 1), l, ((l + r) >> 1));
    update(L, R, V, ((id << 1) | 1), ((l + r) >> 1) + 1, r);
    tree[id] = min(tree[(id << 1)], tree[((id << 1) | 1)]);
  }
  int solve(int id, int l, int r, ll V) {
    push(id, l, r);
    if (l == r) {
      return l;
    }
    push((id << 1), l, ((l + r) >> 1));
    push(((id << 1) | 1), ((l + r) >> 1) + 1, r);
    if (tree[(id << 1)] <= V) {
      return solve((id << 1), l, ((l + r) >> 1), V);
    } else if (tree[((id << 1) | 1)] <= V) {
      return solve(((id << 1) | 1), ((l + r) >> 1) + 1, r, V);
    }
    return 0;
  }
  int query(int L, int R, ll V, int id = 1, int l = 1, int r = n) {
    push(id, l, r);
    if (l > R || r < L) {
      return 0;
    }
    if (L <= l && r <= R) {
      if (tree[id] <= V) {
        return solve(id, l, r, V);
      }
      return 0;
    }
    int ans = query(L, R, V, (id << 1), l, ((l + r) >> 1));
    if (!ans) {
      ans = query(L, R, V, ((id << 1) | 1), ((l + r) >> 1) + 1, r);
    }
    return ans;
  }
} seg;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> d;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] += 1e9;
  }
  if (d == 0) {
    a[n + 1] = inf;
    for (int l = n, r = n; l >= 1; l--) {
      if (a[l] != a[l + 1]) {
        r = l;
      }
      if (best <= r - l + 1) {
        best = r - l + 1;
        ans = {l, r};
      }
    }
    return cout << ans.first << ' ' << ans.second, 0;
  }
  mn.push(0);
  mx.push(0);
  for (int r = 1; r <= n; r++) {
    if (a[r - 1] % d != a[r] % d) {
      lw = r;
    }
    lw = max(lw, pre[a[r]] + 1);
    pre[a[r]] = r;
    while (mn.top() && a[mn.top()] > a[r]) {
      int y = mn.top();
      mn.pop();
      seg.update(mn.top() + 1, y, a[y] - a[r]);
    }
    mn.push(r);
    while (mx.top() && a[mx.top()] < a[r]) {
      int y = mx.top();
      mx.pop();
      seg.update(mx.top() + 1, y, a[r] - a[y]);
    }
    mx.push(r);
    seg.update(r, r, 1ll * r * d);
    int l = seg.query(lw, r, 1ll * (r + k) * d);
    if (best < r - l + 1) {
      best = r - l + 1;
      ans = {l, r};
    }
  }
  cout << ans.first << ' ' << ans.second;
}
