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;
int read() {
  char c = getchar();
  long long x = 1, s = 0;
  while (c < '0' || c > '9') {
    if (c == '-') x = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    s = s * 10 + c - '0';
    c = getchar();
  }
  return s * x;
}
const int N = 8e5 + 55;
int n, k, d, maxx[N * 4], minn[N * 4], pm[N * 4], pi[N * 4], s[N * 4], a[N],
    b[N], c[N], mo[N], tong[N], st[N], pre[N], f[N], qm[N], qi[N], you, top;
void update(int u) {
  maxx[u] = min(maxx[(u << 1)], maxx[(u << 1 | 1)]);
  minn[u] = min(minn[(u << 1)], minn[(u << 1 | 1)]);
  s[u] = min(s[(u << 1)], s[(u << 1 | 1)]);
}
void pushdown(int u, int l, int r) {
  if (pm[u] != 2929810) {
    maxx[(u << 1)] = pm[u] + l;
    maxx[(u << 1 | 1)] = pm[u] + ((l + r) >> 1) + 1;
    s[(u << 1)] = pm[u] + minn[(u << 1)];
    s[(u << 1 | 1)] = pm[u] + minn[(u << 1 | 1)];
    pm[(u << 1)] = pm[(u << 1 | 1)] = pm[u];
    pm[u] = 2929810;
  }
  if (pi[u] != 1919810) {
    minn[(u << 1)] = pi[u] + l;
    minn[(u << 1 | 1)] = pi[u] + ((l + r) >> 1) + 1;
    s[(u << 1)] = pi[u] + maxx[(u << 1)];
    s[(u << 1 | 1)] = pi[u] + maxx[(u << 1 | 1)];
    pi[(u << 1)] = pi[(u << 1 | 1)] = pi[u];
    pi[u] = 1919810;
  }
}
void clear(int u, int l, int r, int x) {
  if (l == r) {
    s[u] = 2e9;
    return;
  }
  pushdown(u, l, r);
  if (x <= ((l + r) >> 1))
    clear((u << 1), l, ((l + r) >> 1), x);
  else
    clear((u << 1 | 1), ((l + r) >> 1) + 1, r, x);
  update(u);
}
void modify(int u, int l, int r, int L, int R, int x) {
  if (r <= you) return;
  if (L <= l and R >= r and you < l) {
    maxx[u] = x + l;
    s[u] = x + minn[u];
    pm[u] = x;
    return;
  }
  pushdown(u, l, r);
  if (L <= ((l + r) >> 1)) modify((u << 1), l, ((l + r) >> 1), L, R, x);
  if (R > ((l + r) >> 1)) modify((u << 1 | 1), ((l + r) >> 1) + 1, r, L, R, x);
  update(u);
}
void change(int u, int l, int r, int L, int R, int x) {
  if (r <= you) return;
  if (L <= l and R >= r and you < l) {
    minn[u] = -x + l;
    s[u] = -x + maxx[u];
    pi[u] = -x;
    return;
  }
  pushdown(u, l, r);
  if (L <= ((l + r) >> 1)) change((u << 1), l, ((l + r) >> 1), L, R, x);
  if (R > ((l + r) >> 1)) change((u << 1 | 1), ((l + r) >> 1) + 1, r, L, R, x);
  update(u);
}
int ask(int u, int l, int r, int v) {
  if (l == r) {
    return l;
  }
  pushdown(u, l, r);
  if (s[(u << 1)] + v <= 0 and you < ((l + r) >> 1))
    return ask((u << 1), l, ((l + r) >> 1), v);
  else
    return ask((u << 1 | 1), ((l + r) >> 1) + 1, r, v);
}
int main() {
  n = read();
  k = read();
  d = read();
  for (int i = 1; i <= n; i++) a[i] = b[i] = mo[i] = read();
  if (d == 0) {
    int qz = 0;
    int maxx = 0, l, r;
    for (int i = 1; i <= n; i++) {
      if (a[i] == a[i - 1])
        qz++;
      else
        qz = 1;
      if (qz > maxx) {
        l = i - qz + 1;
        r = i;
        maxx = qz;
      }
    }
    cout << l << " " << r << endl;
    return 0;
  }
  for (int i = 1; i <= n * 4; i++) pm[i] = 2929810, pi[i] = 1919810;
  int top = n;
  sort(b + 1, b + n + 1);
  top = unique(b + 1, b + n + 1) - b - 1;
  for (int i = 1; i <= n; i++)
    c[i] = lower_bound(b + 1, b + top + 1, a[i]) - b,
    mo[i] = (a[i] % d + d) % d;
  for (int i = 1; i <= n; i++) {
    f[i] = f[i - 1];
    if (tong[c[i]]) {
      f[i] = max(f[i], tong[c[i]]);
    }
    tong[c[i]] = i;
    if (mo[i] == mo[i - 1])
      pre[i] = pre[i - 1];
    else {
      pre[i] = i;
      f[i] = i - 1;
    }
  }
  for (int i = 1; i <= n; i++) {
    while (top and a[st[top]] < a[i]) top--;
    qm[i] = st[top] + 1;
    st[++top] = i;
  }
  top = 0;
  for (int i = 1; i <= n; i++) {
    while (top and a[st[top]] > a[i]) top--;
    qi[i] = st[top] + 1;
    st[++top] = i;
  }
  int maxx = 0, l, r;
  for (int i = 1; i <= n; i++) {
    for (int k = f[i - 1] + 1; k <= f[i]; k++) {
      clear(1, 1, n, k);
    }
    if (i == 9) {
      new char;
    }
    you = f[i];
    modify(1, 1, n, qm[i], i, a[i] / d);
    change(1, 1, n, qi[i], i, a[i] / d);
    int val = ask(1, 1, n, -i - k);
    if (maxx < i - val + 1) {
      maxx = i - val + 1;
      l = val;
      r = i;
    }
  }
  cout << l << " " << r;
  return 0;
}
