762_E. Radio stations_18138
In the lattice points of the coordinate line there are n radio stations, the i-th of which is described by three integers:

  * xi — the coordinate of the i-th station on the line, 
  * ri — the broadcasting range of the i-th station, 
  * fi — the broadcasting frequency of the i-th station. 



We will say that two radio stations with numbers i and j reach each other, if the broadcasting range of each of them is more or equal to the distance between them. In other words min(ri, rj) ≥ |xi - xj|.

Let's call a pair of radio stations (i, j) bad if i < j, stations i and j reach each other and they are close in frequency, that is, |fi - fj| ≤ k.

Find the number of bad pairs of radio stations.

Input

The first line contains two integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the number of radio stations and the maximum difference in the frequencies for the pair of stations that reach each other to be considered bad.

In the next n lines follow the descriptions of radio stations. Each line contains three integers xi, ri and fi (1 ≤ xi, ri ≤ 109, 1 ≤ fi ≤ 104) — the coordinate of the i-th radio station, it's broadcasting range and it's broadcasting frequency. No two radio stations will share a coordinate.

Output

Output the number of bad pairs of radio stations.

Examples

Input

3 2
1 3 10
3 2 5
4 10 8


Output

1


Input

3 3
1 3 10
3 2 5
4 10 8


Output

2


Input

5 1
1 3 2
2 2 4
3 2 1
4 2 1
5 3 3


Output

2


Input

5 1
1 5 2
2 5 4
3 5 1
4 5 1
5 5 3


Output

5
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> v[N];
int n, k, b[N], rot[N], tot;
long long ans;
int lson[N * 20], rson[N * 20], s[N * 20];
struct node {
  int xi, ri, fi;
} a[N];
bool cmp(node A, node B) { return A.ri > B.ri; }
int lp(int x) { return lower_bound(b + 1, b + 1 + n, x) - b; }
int up(int x) { return upper_bound(b + 1, b + 1 + n, x) - b; }
void ins(int &rt, int l, int r, int x) {
  if (!rt) rt = ++tot;
  s[rt]++;
  int mid = l + r >> 1;
  if (l == r) return;
  if (x <= mid)
    ins(lson[rt], l, mid, x);
  else
    ins(rson[rt], mid + 1, r, x);
}
int query(int rt, int l, int r, int x, int y) {
  if (!rt) return 0;
  if (x <= l && r <= y) return s[rt];
  int mid = l + r >> 1, t = 0;
  if (x <= mid) t += query(lson[rt], l, mid, x, y);
  if (mid < y) t += query(rson[rt], mid + 1, r, x, y);
  return t;
}
signed main() {
  scanf("%d %d", &n, &k);
  for (register int i = (1); i <= (n); ++i)
    scanf("%d %d %d", &a[i].xi, &a[i].ri, &a[i].fi), b[i] = a[i].xi;
  sort(a + 1, a + 1 + n, cmp);
  sort(b + 1, b + 1 + n);
  for (register int i = (1); i <= (n); ++i) {
    int x = lp(a[i].xi - a[i].ri), y = up(a[i].xi + a[i].ri) - 1;
    y = min(y, n);
    for (register int j = (a[i].fi - k); j <= (a[i].fi + k); ++j)
      if (j >= 1) ans += query(rot[j], 1, n, x, y);
    ins(rot[a[i].fi], 1, n, lp(a[i].xi));
  }
  printf("%lld\n", ans);
  return 0;
}
