eolymp
bolt
Try our new interface for solving problems

Ring

Time limit 2 seconds
Memory limit 256 MiB

There's a colored ring on the table. The ring has k sectors, and i-th sector has color i (all k colors are pairwise distinct). Sectors are numbered consecutively in clockwise direction. Kanga allowed Baby Roo to write n different integers from 1 to n on the ring. Number i should be written either on sector with color x_i, said Kanga, or on any other that is at most a_i sectors counterclockwise far from x_i or at most b_i sectors clockwise far.

Kanga said that the numbers are written correctly if the above restrictions are met, each sector has at most one number written on it and the numbers 1, 2, ..., n are ordered in clockwise direction: if we start from the sector where we wrote 1 and go clockwise, we meet the other numbers in order 2, 3, ..., n and then 1 again.

Now Baby Roo wants to know how many different ways are there to spoil the colored ring by writing the numbers correctly. Please note that it doesn't matter what number you write on the sector to get it spoiled.

Input data

First line contains two integers n and k (1n15, 1k60, nk). Each of the next n lines contains three integers x_i, a_i, b_i (1x_ik; 0a_i, b_i; a_i+b_i < k). The numbers x_i are sorted in strictly increasing order.

Output data

Output the number of different ways to spoil the ring.

Examples

Input example #1
1 5
1 2 1
Output example #1
4