{"raw_statement":[{"iden":"statement","content":"The mafia is finally resting after a year of hard work and not so much money. Mafianca, the little mascot of the gang wanted to go to the beach.\n\nLittle did they know that the rival gang had prepared a trap to the little girl and her rubber duck. They know that Mafianca, despite loving the beach, hates water. So they set up some water sprayers to ruin her day. The beach can be seen as a plane. The sprayers are located at different (x, y) points along the shore. Each sprayer is so strong that it creates an infinite line of water, reaching every point with x-coordinate equal to the sprayer.\n\nMafianca's bodyguards figured this plan out. They didn't have the time to destroy the sprayers, so they decided to do something else. Lying around on the beach was a piece of modern art: a bunch of walls, represented by horizontal line segments, painted by some futuristic anonymous artist. Those walls can be moved, but they can only be moved together and horizontally. \n\nThe bodyguards decided that they would try to move this piece of art in order to block the most sprayers they can. A sprayer is blocked if there's at least one wall in both of its sides. \n\nHow many sprayers can they block?\n\nInput begins with the number of sprayers, n (1 ≤ n ≤ 1000) and the number of walls in the modern art, m (1 ≤ m ≤ 1000). \n\nFollows n lines, each with two intergers, y and x (0 ≤ y, x ≤ 106), indicating that there's a sprayer at position x, y. \n\nThen follows m lines, each with three integers: y, xbegin and xend (0 ≤ y ≤ 106) and (0 ≤ xbegin < xend ≤ 106) denoting a wall in the modern art has y-coordinate y, begins at xbegin and ends at xend. No wall will have a y-coordinate shared with a sprayer and the walls with same y will not intersect.\n\nPrint the number of sprayers that can be blocked.\n\nIn the test case #4, the beach looks like this:\n\nA solution would be\n\n"},{"iden":"input","content":"Input begins with the number of sprayers, n (1 ≤ n ≤ 1000) and the number of walls in the modern art, m (1 ≤ m ≤ 1000). Follows n lines, each with two intergers, y and x (0 ≤ y, x ≤ 106), indicating that there's a sprayer at position x, y. Then follows m lines, each with three integers: y, xbegin and xend (0 ≤ y ≤ 106) and (0 ≤ xbegin < xend ≤ 106) denoting a wall in the modern art has y-coordinate y, begins at xbegin and ends at xend. No wall will have a y-coordinate shared with a sprayer and the walls with same y will not intersect."},{"iden":"output","content":"Print the number of sprayers that can be blocked."},{"iden":"examples","content":"Input1 12 23 1 3Output0Input2 52 32 61 0 24 0 40 2 31 4 53 5 7Output2Input4 52 32 82 205 11 0 24 0 40 2 31 4 53 5 7Output2Input3 42 02 44 71 0 23 1 35 0 25 3 4Output2"},{"iden":"note","content":"In the test case #4, the beach looks like this:  A solution would be  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of favorite words.  \nLet $ M \\in \\mathbb{Z}^+ $ be the number of changes.  \nLet $ W = (w_1, w_2, \\dots, w_N) $ be the ordered list of favorite words, where each $ w_i \\in \\Sigma^* $ and $ |w_i| \\leq 100 $.  \nLet $ S \\in \\Sigma^* $ be the song string, with $ |S| \\leq 100000 $, indexed from 1.  \nLet $ \\text{LCP}(u, v) $ denote the length of the longest common prefix of strings $ u $ and $ v $.  \nGiven constraint: $ \\sum_{i=1}^N |w_i| - \\sum_{i=1}^{N-1} \\text{LCP}(w_i, w_{i+1}) \\leq 100 $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 100 $  \n2. $ 1 \\leq M \\leq 100000 $  \n3. $ |S| \\leq 100000 $  \n4. Each change: $ 1 \\leq \\text{pos} \\leq |S| $, $ c \\in \\Sigma $  \n5. $ \\sum_{i=1}^N |w_i| - \\sum_{i=1}^{N-1} \\text{LCP}(w_i, w_{i+1}) \\leq 100 $\n\n**Objective**  \nDefine the number of favorite words **used at the beginning** of $ S $ as the maximum number $ k \\in \\{0, 1, \\dots, N\\} $ such that there exists a decomposition of a prefix of $ S $ into $ k $ consecutive non-overlapping substrings, each equal to one of $ w_1, \\dots, w_k $, in order (i.e., $ w_1 $, then $ w_2 $, ..., up to $ w_k $), with no gaps or overlaps.\n\nAfter each of the $ M $ character updates to $ S $, recompute this maximum $ k $.\n\nOutput $ M+1 $ values: the initial count, then the count after each change.","simple_statement":"You are given a list of favorite words and a song string. You need to count how many of the favorite words appear as prefixes of the song. After each letter change in the song, update and output the count. Output the initial count and the count after each change.","has_page_source":false}