{"raw_statement":[{"iden":"statement","content":"When the monkey professor leaves his class for a short time, all the monkeys go bananas. N monkeys are lined up sitting side by side on their chairs. They each have the same joke book. Before the professor returns, M jokes were heard.\n\nEach of the M jokes are said in the order given and have the following properties:\n\nxi - position of the monkey who said it.\n\nli – index of the joke in the book.\n\nki – volume the monkey says that joke.\n\nWhen the monkey at position xi says the joke li, all monkeys at a distance less than or equal to ki from that monkey (including the monkey who said the joke) will fall off their chairs in laughter if they have never heard the joke li before.\n\nIf the joke li has been heard anytime during the past before, and the monkey hears it again, then he will sit back up in his chair.\n\nA monkey can fall off his chair more than once (every time he hears a new joke), and if he is already on the ground and hears a new joke, he will stay on the ground.\n\nCan you figure out how many monkeys will be in their seats by the time the professor comes back?\n\nThe first line of input is T – the number of test cases.\n\nThe first line of each test case is N, M (1 ≤ N ≤ 105) (1 ≤ M ≤ 105) – the number of monkeys in the class, and the number of jokes said before the professor returns.\n\nThe next M lines contain the description of each joke: xi, li, ki (1 ≤ xi ≤ N) (1 ≤ li ≤ 105) (0 ≤ ki ≤ N).\n\nFor each test case, output on a line a single integer - the number of monkeys in their seats after all jokes have been said.\n\n"},{"iden":"input","content":"The first line of input is T – the number of test cases.The first line of each test case is N, M (1 ≤ N ≤ 105) (1 ≤ M ≤ 105) – the number of monkeys in the class, and the number of jokes said before the professor returns.The next M lines contain the description of each joke: xi, li, ki (1 ≤ xi ≤ N) (1 ≤ li ≤ 105) (0 ≤ ki ≤ N)."},{"iden":"output","content":"For each test case, output on a line a single integer - the number of monkeys in their seats after all jokes have been said."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of monkeys, indexed $ 1 $ to $ N $.  \n- Let $ M \\in \\mathbb{Z} $ be the number of jokes.  \n- Let $ J = \\{(x_i, l_i, k_i) \\mid i \\in \\{1, \\dots, M\\}\\} $ be the sequence of jokes, where:  \n  - $ x_i \\in \\{1, \\dots, N\\} $: position of the monkey who says the joke.  \n  - $ l_i \\in \\mathbb{Z}^+ $: joke identifier.  \n  - $ k_i \\in \\{0, \\dots, N\\} $: volume (radius of effect).  \n\nLet $ S \\subseteq \\{1, \\dots, N\\} $ be the set of monkeys currently seated (initially $ S = \\{1, \\dots, N\\} $).  \nLet $ H \\subseteq \\mathbb{Z}^+ $ be the set of jokes that have been heard at least once.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unspecified} $  \n2. $ 1 \\le N \\le 10^5 $  \n3. $ 1 \\le M \\le 10^5 $  \n4. $ 1 \\le x_i \\le N $  \n5. $ 1 \\le l_i \\le 10^5 $  \n6. $ 0 \\le k_i \\le N $  \n\n**Objective**  \nProcess each joke $ (x_i, l_i, k_i) $ in order:  \n- Let $ R_i = \\{ j \\in \\{1, \\dots, N\\} \\mid |j - x_i| \\le k_i \\} $ be the set of monkeys affected by joke $ i $.  \n- If $ l_i \\notin H $:  \n  - Remove from $ S $ all $ j \\in R_i $ (they fall off).  \n  - Add $ l_i $ to $ H $.  \n- Else (i.e., $ l_i \\in H $):  \n  - Add to $ S $ all $ j \\in R_i $ who are not currently seated (they sit back up).  \n\nOutput the size of $ S $ after processing all $ M $ jokes.","simple_statement":"There are N monkeys in a row. M jokes are told one by one. Each joke is told by monkey at position x, is joke number l, and has volume k. When joke l is told, all monkeys within distance k from x (including x) will fall down if they haven't heard joke l before. If they already heard joke l, they stand up. Monkeys can fall and stand multiple times. After all jokes, how many monkeys are still sitting?","has_page_source":false}