{"raw_statement":[{"iden":"statement","content":"2 years have passed now since *Bakkar*'s graduation. He has completed his military service period and happily got married to *Maymona*. Next week is *Bakkar* & *Maymona*'s anniversary and fortunately *Bakkar* has a gift in mind for *Maymona*. He wants to buy her a new smartphone as hers was stolen on her way home in the metro. \n\n*Bakkar* wants to make *Maymona* happy as much as he can. So a couple days ago he had a conversation with her about her preferable specs in a smartphone. He noticed that *Maymona* cares the most about the following four properties: height, width, thickness and weight.\n\n*Bakkar* also has a very important fifth property which is the price of the smartphone. So *Bakkar* started to search the internet for the available smartphones. He was shocked by the variety of smartphones available (up to 10,000 phones). So *Bakkar* started filtering the phones list to get only the phones that satisfies the four properties that *Maymona* cares about while taking into consideration the price range. His goal now is to find how many smartphones match these criteria so he can take other hints from *Maymona* to further filter them. Given *Maymona*'s preference ranges for the 4 properties that she cares about, *Bakkar*'s price range that he can afford and a list of available phones each with its corresponding properties (height, width, thickness, weight and price), *Bakkar* as a Software Engineer will write a short program to filter the list of the smartphones to match *Maymona*'s and his preferences. The program will output the number of smartphones that matches their preferences.\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  50). Followed by *T* test cases. The first line of each testcase contains two integer *N* and *Q*, the number of smartphones and the number of queries respectively(1  ≤  *N*,*Q*  ≤  104).\n\n*N* lines follow, each line represents the properties of a single phone. Each one containing 5 floating point numbers *p*, *h*, *w*, *t*, *we*, representing the price, height, width, thickness and weight. Each number will have at most 3 decimal places. (0.000  ≤  *p*, *h*, *w*, *t*, *we*  ≤  5000.000). For each test case, there is no more than 10 different values for each of the price, height, width, thickness and weight.\n\n*Q* lines follow, each line representing a query. Each one containing 10 floating point numbers *p_low*, *h_low*, *w_low*, *t_low*, *we_low*, *p_hi*, *h_hi*, *w_hi*, *t_hi*, *we_hi*, representing the lower and upper bounds of the properties. Each number will have at most 3 decimal places. (0.000  ≤  *p_low*, *h_low*, *w_low*, *t_low*, *we_low*, *p_hi*, *h_hi*, *w_hi*, *t_hi*, *we_hi*,  ≤  5000.000). *p_low*  ≤  *p_hi*; *h_low*  ≤  *h_hi*; *w_low*  ≤  *w_hi*; *t_low*  ≤  *t_hi*; *we_low*  ≤  *we_hi*.\n\nFor each test case print a line containing \"Case n:\" (without the quotes) where n is the test case number (starting from 1) followed by *Q* lines, each line contains a single integer, the number of smartphones that matches the query's preferences. A phone matches the query if and only if its value in every property lies between the lower and upper bounds of the query preference inclusive. \n\n*Warning: large Input/Output data, be careful with certain languages.*\n\n"},{"iden":"input","content":"Your program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  50). Followed by *T* test cases. The first line of each testcase contains two integer *N* and *Q*, the number of smartphones and the number of queries respectively(1  ≤  *N*,*Q*  ≤  104).*N* lines follow, each line represents the properties of a single phone. Each one containing 5 floating point numbers *p*, *h*, *w*, *t*, *we*, representing the price, height, width, thickness and weight. Each number will have at most 3 decimal places. (0.000  ≤  *p*, *h*, *w*, *t*, *we*  ≤  5000.000). For each test case, there is no more than 10 different values for each of the price, height, width, thickness and weight.*Q* lines follow, each line representing a query. Each one containing 10 floating point numbers *p_low*, *h_low*, *w_low*, *t_low*, *we_low*, *p_hi*, *h_hi*, *w_hi*, *t_hi*, *we_hi*, representing the lower and upper bounds of the properties. Each number will have at most 3 decimal places. (0.000  ≤  *p_low*, *h_low*, *w_low*, *t_low*, *we_low*, *p_hi*, *h_hi*, *w_hi*, *t_hi*, *we_hi*,  ≤  5000.000). *p_low*  ≤  *p_hi*; *h_low*  ≤  *h_hi*; *w_low*  ≤  *w_hi*; *t_low*  ≤  *t_hi*; *we_low*  ≤  *we_hi*."},{"iden":"output","content":"For each test case print a line containing \"Case n:\" (without the quotes) where n is the test case number (starting from 1) followed by *Q* lines, each line contains a single integer, the number of smartphones that matches the query's preferences. A phone matches the query if and only if its value in every property lies between the lower and upper bounds of the query preference inclusive. "},{"iden":"examples","content":"Input110 35.0 6.0 6.0 5.0 4.01.0 9.0 3.0 8.0 0.01.0 7.0 7.0 5.0 5.04.0 0.0 1.0 9.0 8.06.0 0.0 5.0 6.0 0.06.0 7.0 6.0 5.0 4.01.0 4.0 5.0 6.0 6.05.0 7.0 8.0 9.0 8.01.0 3.0 3.0 7.0 9.01.0 2.0 8.0 4.0 8.00.0 1.0 2 3.0 4 5.0 6.0 7.0 8.0 9.04.0 0.0 1.0 5 0.0 6.0 7.0 6 9.0 8.03.0 2.0 5 7.0 8.0 5.0 5.0 6 8.0 9.0OutputCase 1:340"},{"iden":"note","content":"*Warning: large Input/Output data, be careful with certain languages.*"}],"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 $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N, Q \\in \\mathbb{Z} $ denote the number of smartphones and queries, respectively.  \n- Let $ P = \\{ (p_i, h_i, w_i, t_i, we_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of smartphones, where each tuple represents price, height, width, thickness, and weight.  \n- Let $ Q_k = \\{ (p_{\\text{low},j}, h_{\\text{low},j}, w_{\\text{low},j}, t_{\\text{low},j}, we_{\\text{low},j}, p_{\\text{hi},j}, h_{\\text{hi},j}, w_{\\text{hi},j}, t_{\\text{hi},j}, we_{\\text{hi},j}) \\mid j \\in \\{1, \\dots, Q\\} \\} $ be the set of queries.\n\n**Constraints**  \n1. $ 1 \\le T \\le 50 $  \n2. For each test case:  \n   - $ 1 \\le N, Q \\le 10^4 $  \n   - $ 0.000 \\le p_i, h_i, w_i, t_i, we_i \\le 5000.000 $ for all $ i \\in \\{1, \\dots, N\\} $  \n   - $ 0.000 \\le p_{\\text{low},j} \\le p_{\\text{hi},j} \\le 5000.000 $, and similarly for $ h, w, t, we $, for all $ j \\in \\{1, \\dots, Q\\} $  \n   - Each property has at most 10 distinct values across all smartphones.  \n\n**Objective**  \nFor each test case $ k $ and each query $ j $, compute:  \n$$\n\\left| \\left\\{ i \\in \\{1, \\dots, N\\} \\ \\middle| \\ \n\\begin{array}{c}\np_{\\text{low},j} \\le p_i \\le p_{\\text{hi},j} \\\\\nh_{\\text{low},j} \\le h_i \\le h_{\\text{hi},j} \\\\\nw_{\\text{low},j} \\le w_i \\le w_{\\text{hi},j} \\\\\nt_{\\text{low},j} \\le t_i \\le t_{\\text{hi},j} \\\\\nwe_{\\text{low},j} \\le we_i \\le we_{\\text{hi},j}\n\\end{array}\n\\right\\} \\right|\n$$","simple_statement":"Given N phones, each with 5 properties: price, height, width, thickness, weight.  \nFor Q queries, each query gives 5 lower and upper bounds for these properties.  \nFor each query, count how many phones have all 5 properties within the given ranges (inclusive).","has_page_source":false}