Problem: In the last mission, MDCS has successfully shipped N AI robots to Mars. Before they start exploring, system initialization is required so they are arranged in a line. Every robot can be described with three numbers: position (x_i), radius of sight (r_i) and IQ (q_i).

Since they are intelligent robots, some of them will talk if they see each other. Radius of sight is inclusive, so robot can see other all robots in range [x_i - r_i, x_i + r_i]. But they don't walk to talk with anybody, but only with robots who have similar IQ. By similar IQ we mean that their absolute difference isn't more than K. 

Help us and calculate how many pairs of robots are going to talk with each other, so we can timely update their software and avoid any potential quarrel.

Input

The first line contains two integers, numbers N (1 ≤ N ≤ 10^5)  and K (0 ≤ K ≤ 20).

Next N lines contain three numbers each x_i, r_i, q_i (0 ≤ x_i,r_i,q_i ≤ 10^9) — position, radius of sight and IQ of every robot respectively.

Output

Output contains only one number — solution to the problem.

Example

Input

3 2
3 6 1
7 3 10
10 5 8


Output

1

Note

The first robot can see the second, but not vice versa. The first robot can't even see the third. The second and the third robot can see each other and their IQs don't differ more than 2 so only one conversation will happen.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class G implements Runnable{
	public static void main (String[] args) {new Thread(null, new G(), "_cf", 1 << 28).start();}

	int n, k;
	int[] xs, rs, qs, loc, Ls, Rs;
	int[][] order, search;
	long res;
	HashMap<Integer, Integer> in;
	BIT bit;
	
	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		long start = System.nanoTime();
		
		in = new HashMap<>();
		n = fs.nextInt();
		k = fs.nextInt();
		xs = new int[n];
		rs = new int[n];
		qs = new int[n];
		
		order = new int[n][2];
		search = new int[n][3];
		
		for(int i = 0; i < n; i++) {
			xs[i] = fs.nextInt();
			rs[i] = fs.nextInt();
			qs[i] = fs.nextInt();
			if(!in.containsKey(qs[i])) {
				in.put(qs[i], in.size());
			}
			order[i][0] = rs[i];
			order[i][1] = i;
			search[i][0] = qs[i];
			search[i][1] = xs[i];
			search[i][2] = i;
		}
		
		Arrays.sort(order, (a, b) -> Integer.compare(b[0], a[0]));
		Arrays.sort(search, (a, b) -> 
		Integer.compare(a[0], b[0]) == 0 ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
		
		int mm = in.size();
		Ls = new int[mm];
		Rs = new int[mm];
		for(int i = 0; i < n; i++) {
			int j = i;
			while(j < n && search[i][0] == search[j][0]) j++;
			int x = in.get(search[i][0]);
			Ls[x] = i; Rs[x] = j-1;
			i = j-1;
		}
		
		//okay now we have an array of robots sorted by biggest radius to smallest
		//and we have an array of robots sorted by smallest IQ to largest and
		// break ties with the smaller position
		
		//the smart solution:
		//let's process the robots in decreasing order of radii. And for each
		//possible IQ (only 40) we'll find the left and right points of that IQ
		//in the search array (since it's sorted). From here, we can binary
		//search that chunk of the array to find the left most point I can
		//hit and the right most point I can hit.
		
		//To find the people that I could speak with, I query my bit on those
		//compressed positions and the value there is everyone I can speak with.
		//I don't need to worry about those people being able to speak with me
		//since we get updated in order of decreasing radii. So if I can see someone
		//and he definitely has a radius >= mine, then he can also without a doubt
		//see me.

		//loc[i] is the location of index i in the search array
		//I need this to update my bit.
		loc = new int[n];
		for(int i = 0; i < n; i++) {
			loc[search[i][2]] = i;
		}
		
		res = 0;
		bit = new BIT(n);
		for(int i = 0; i < n; i++) {
			int radius = order[i][0];
			int idx = order[i][1];
			solve(radius, idx);
			bit.update(loc[idx]+1, 1);
		}
		out.println(res);
		out.close();
	}

	void solve(int radius, int index) {
		int left = xs[index] - radius;
		int right = xs[index] + radius;
		for(int niq = qs[index] - k; niq <= qs[index] + k; niq++) {
			if(!in.containsKey(niq)) continue;
			int x = in.get(niq);
			int leftIQ = Ls[x];
			int rightIQ = Rs[x];
			int leftBound = bound(leftIQ, rightIQ, left, true);
			int rightBound = bound(leftIQ, rightIQ, right, false);
			if(leftBound == rightIQ+1 || rightBound == leftIQ-1) continue;
			int sum = bit.sum(rightBound+1);
			sum -= bit.sum(leftBound);
			res += sum;
		}
	}
	
	int bound(int lo, int hi, int val, boolean bigger) {
		int res = bigger ? hi+1 : lo-1;
		for(int bs = 0; bs < 50 && lo <= hi; bs++) {
			int mid = (lo + hi) / 2;
			if(bigger) {
				if(search[mid][1] < val) lo = mid+1;
				else {
					res = mid;
					hi = mid-1;
				}
			}
			else {
				if(search[mid][1] > val) hi = mid-1;
				else {
					res = mid;
					lo = mid+1;
				}
			}
		}
		return res;
	}
	
	public class BIT {
		
		int[] bit;
		int n;
		
		public BIT(int a) {
			n = a + 1;
			bit = new int[n];
		}
		
		//Remember that when querying a sum to query the 1-based index of the value.
		
		void update (int index, int val) {
			while(index < n) {
				bit[index] += val;
				index += (index & (-index));
			}
		}
		
		int sum (int index) {
			int sum = 0;
			while(index > 0) {
				sum += bit[index];
				index -= (index & (-index));
			}
			return sum;
		}
	}


	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}