The first line contains two integers, h and d
(1 ≤ h ≤ 100,000; 1 ≤ d ≤ 100,000), representing the number of houses and the number of days that Santa pranked the South Pole that year, respectively. The next d lines each contain three integers, s, k, and p (1 ≤ s ≤ h; 2 ≤ k ≤ 10; 1 ≤ p ≤ h), denoting the starting house, the number representing his frequency of visiting houses (he skips k-1 houses), and the maximum number of houses he pranks that day. Note that he will visit p houses unless he passes the very last house.