{"raw_statement":[{"iden":"statement","content":"The Gregorian calendar is internationally the most widely used civil calendar. It is named after Pope Gregory XIII, who introduced it in October 1582.\n\nIn the Gregorian calendar, there are 28 days in February in a common year and 29 days in February in a leap year. Year Y is a leap year if and only if Y is a multiple of 400, or Y is a multiple of 4 and is not a multiple of 100.\n\nPercy is curious about the distribution of days of the week of his birthday in his life. By checking the calendar, he quickly finds that in the years between 1999 and 2017 (inclusive), his birthday (in case you do not know, 27 February) appears only twice on both Tuesday and Thursday, three times on each of the other days of the week. \n\nPercy finds counting the distribution of some days in some consecutive years really cool, so he decides to invent a way to quickly count the distribution.\n\nWithin 15 minutes, he successfully invented a fast program to do the calculation for years between 1583 and 2 × 109, inclusive. His program can answer 5000 queries in 1 second. However, he is not sure if the program works correctly, so he needs your help. Your task is simple, write your own program to do the calculation, so that Percy can check his program's correctness by comparing the outputs of different queries with your program.\n\nIn this problem, please assume the definition of leap years mentioned above is true for all years between 1583 and 2 × 109, inclusive.\n\nThe first line consists of a single integer, Q, denotes the number of queries. (1 ≤ Q ≤ 5000)\n\nIn the next Q lines, each describes a single query. The queries are in the format _S E M D_, which means you have to calculate the distribution of days of the week for the D-th day of the M-th month for all years between S and E, inclusive. (1583 ≤ S ≤ E ≤ 2 × 109, the days given are one of the 366 valid days)\n\nOutput Q lines, each answers a query given.\n\nIn each line output 7 integers, the frequencies of days of the weeks in this order: Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday.\n\nThe order of answers should follow the order of queries given.\n\n"},{"iden":"input","content":"The first line consists of a single integer, Q, denotes the number of queries. (1 ≤ Q ≤ 5000)In the next Q lines, each describes a single query. The queries are in the format _S E M D_, which means you have to calculate the distribution of days of the week for the D-th day of the M-th month for all years between S and E, inclusive. (1583 ≤ S ≤ E ≤ 2 × 109, the days given are one of the 366 valid days)"},{"iden":"output","content":"Output Q lines, each answers a query given.In each line output 7 integers, the frequencies of days of the weeks in this order: Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday.The order of answers should follow the order of queries given."},{"iden":"examples","content":"Input11999 2017 2 27Output3 3 2 3 2 3 3Input22017 2017 8 152017 2021 2 29Output0 0 1 0 0 0 00 0 0 0 0 0 1Input43141 5926 5 35897 9323 8 42718 2818 2 82222 2222 2 22Output404 391 403 390 404 396 398488 488 497 481 497 480 49615 14 14 15 14 15 140 0 0 0 0 1 0"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query $ q \\in \\{1, \\dots, Q\\} $, let:  \n- $ S_q, E_q \\in \\mathbb{Z} $ with $ 1583 \\leq S_q \\leq E_q \\leq 2 \\times 10^9 $ be the range of years.  \n- $ M_q \\in \\{1, \\dots, 12\\} $ be the month.  \n- $ D_q \\in \\{1, \\dots, 366\\} $ be the day of the month (valid day in some year).  \n\nDefine the leap year function $ L(Y) $:  \n$$\nL(Y) = \n\\begin{cases}\n1 & \\text{if } Y \\equiv 0 \\pmod{400} \\text{ or } (Y \\equiv 0 \\pmod{4} \\text{ and } Y \\not\\equiv 0 \\pmod{100}) \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\nDefine the number of days in month $ M $ in year $ Y $:  \n$$\n\\text{days}(M, Y) = \n\\begin{cases}\n29 & \\text{if } M = 2 \\text{ and } L(Y) = 1 \\\\\n28 & \\text{if } M = 2 \\text{ and } L(Y) = 0 \\\\\n31 & \\text{if } M \\in \\{1,3,5,7,8,10,12\\} \\\\\n30 & \\text{otherwise}\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\leq Q \\leq 5000 $  \n2. For each query:  \n   - $ 1583 \\leq S_q \\leq E_q \\leq 2 \\times 10^9 $  \n   - $ 1 \\leq M_q \\leq 12 $  \n   - $ 1 \\leq D_q \\leq \\text{days}(M_q, Y) $ for all $ Y \\in [S_q, E_q] $ (i.e., $ D_q $ is valid for all years in range)  \n\n**Objective**  \nFor each query $ q $, compute the frequency vector $ \\vec{f}_q = (f_{q,0}, f_{q,1}, \\dots, f_{q,6}) $, where:  \n- $ f_{q,i} $ is the number of years $ Y \\in [S_q, E_q] $ such that the $ D_q $-th day of month $ M_q $ in year $ Y $ falls on day of week $ i $,  \n- with $ i = 0 $ for Sunday, $ i = 1 $ for Monday, ..., $ i = 6 $ for Saturday.  \n\nOutput $ \\vec{f}_q $ for each query in order.","simple_statement":"Given Q queries, for each query with S, E, M, D, count how many times the D-th day of month M falls on each day of the week (Sunday to Saturday) from year S to year E inclusive. Output 7 integers per query: counts for Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday.","has_page_source":false}