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 = 200006;
inline char nc() {
  static char buf[100000], *i = buf, *j = buf;
  return i == j && (j = (i = buf) + fread(buf, 1, 100000, stdin), i == j)
             ? EOF
             : *i++;
}
inline int _read() {
  char ch = nc();
  int sum = 0, p = 1;
  while (ch != '-' && !(ch >= '0' && ch <= '9')) ch = nc();
  if (ch == '-') p = -1, ch = nc();
  while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = nc();
  return sum * p;
}
int n, m, K, D, top1, top2, ans1, ans2, pr[maxn], stack1[maxn], stack2[maxn],
    tem[maxn], a[maxn], b[maxn];
long long X[maxn * 4], tag[maxn * 4];
bool vis[maxn];
void add(int p, long long k) {
  tag[p] += k;
  X[p] += k;
}
void pushdown(int p) {
  if (tag[p]) {
    add(p << 1, tag[p]), add(p << 1 | 1, tag[p]), tag[p] = 0;
  }
}
void update(int L, int R, long long k, int p = 1, int l = 1, int r = n) {
  if (l > R || r < L) return;
  if (L <= l && R >= r) return add(p, k);
  pushdown(p);
  int mid = l + r >> 1;
  update(L, R, k, p << 1, l, mid);
  update(L, R, k, p << 1 | 1, mid + 1, r);
  X[p] = min(X[p << 1], X[p << 1 | 1]);
}
int query(int L, int R, long long k, int p = 1, int l = 1, int r = n) {
  if (l > R || r < L) return -1;
  if (l == r) return l;
  int mid = l + r >> 1;
  pushdown(p);
  int pos = -1;
  if (X[p << 1 | 1] <= k) pos = query(L, R, k, p << 1 | 1, mid + 1, r);
  if (pos == -1 && X[p << 1] <= k) pos = query(L, R, k, p << 1, l, mid);
  return pos;
}
void push(int k) {
  while (top1 && a[stack1[top1]] < a[k])
    update(stack1[top1], stack1[top1 - 1] - 1,
           tem[a[k]] - tem[a[stack1[top1]]]),
        top1--;
  stack1[++top1] = k;
  while (top2 && a[stack2[top2]] > a[k])
    update(stack2[top2], stack2[top2 - 1] - 1,
           tem[a[stack2[top2]]] - tem[a[k]]),
        top2--;
  stack2[++top2] = k;
}
void print() {
  ans1 = 0;
  ans2 = -1;
  for (int i = 1; i <= n; i++) a[i] = _read();
  for (int i = 1, j = 1; i <= n; i = j) {
    for (; j <= n && a[j] == a[i]; j++)
      ;
    if (j - i > ans2 - ans1 + 1) ans1 = i, ans2 = j - 1;
  }
  printf("%d %d", ans1, ans2);
  exit(0);
}
int main() {
  n = _read();
  K = _read();
  D = _read();
  if (!D) print();
  for (int i = 1; i <= n; i++)
    tem[i] = a[i] = _read(), b[i] = (a[i] % D + D) % D;
  sort(tem + 1, tem + 1 + n);
  m = unique(tem + 1, tem + 1 + n) - tem - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(tem + 1, tem + 1 + m, a[i]) - tem;
  for (int i = 1, j = 0; i <= n; i++) {
    while (j < n && b[j + 1] == b[i] && !vis[a[j + 1]]) vis[a[++j]] = 1;
    pr[i] = j;
    vis[a[i]] = 0;
  }
  update(n, n, -(long long)D * n);
  stack1[0] = stack2[0] = n + 1;
  stack1[top1 = 1] = n;
  stack2[top2 = 1] = n;
  for (int i = n - 1; i >= 1; i--) {
    update(i, i, -(long long)D * i);
    push(i);
    int pos = query(i, pr[i], (long long)D * (K - i));
    if (pos >= i && pos <= pr[i] && pos - i >= ans2 - ans1)
      ans1 = i, ans2 = pos;
  }
  return printf("%d %d", ans1, ans2), 0;
}
