{"raw_statement":[{"iden":"statement","content":"...Neo finally understood how The Matrix is working.\n\nThe Matrix is the square grid n × n; each cell of the grid contains 0 or 1. Next additional limitations are working for The Matrix:\n\nThe Matrix changes with time following next law: lets define #cf_span(class=[tex-font-style-underline], body=[state]) of The Matrix as sequence of n2 elements (a1, 1, ..., a1, n, a2, 1, ..., an, n), obtained from The Matrix by writing all its lines one by one. Then all states, corresponding to correct (i.e. conforming with limitations above) instances of The Matrix, are ordered lexicographcally and in time t The Matrix have t-th state in the resulting list.\n\nNeo is sure that he can reconstruct the Matrix in any moment of time. Can you do it?\n\nFirst line of the input contains four integers n, a, b and q (1 ≤ n ≤ 10, 1 ≤ a ≤ b ≤ n, 1 ≤ q ≤ 1000) — dimension of The Matrix, parameters of The Matrix and number of queries, respectively. i-th of the next q lines contains one integer ti — some moment of time (1 ≤ ti ≤ 1018).\n\nFor i-th request print n lines, each containing n characters — The Matrix in the time ti. If total number of correct instances of the Matrix is less than ti, print \"_No such matrix._\" without quotes. Separate answers on different requests with newline. Follow the sample for clarify. \n\n"},{"iden":"input","content":"First line of the input contains four integers n, a, b and q (1 ≤ n ≤ 10, 1 ≤ a ≤ b ≤ n, 1 ≤ q ≤ 1000) — dimension of The Matrix, parameters of The Matrix and number of queries, respectively. i-th of the next q lines contains one integer ti — some moment of time (1 ≤ ti ≤ 1018)."},{"iden":"output","content":"For i-th request print n lines, each containing n characters — The Matrix in the time ti. If total number of correct instances of the Matrix is less than ti, print \"_No such matrix._\" without quotes. Separate answers on different requests with newline. Follow the sample for clarify. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, a, b, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10 $, $ 1 \\leq a \\leq b \\leq n $, $ 1 \\leq q \\leq 1000 $.  \nLet $ \\mathcal{M} $ be the set of all $ n \\times n $ binary matrices (entries in $ \\{0,1\\} $) such that the number of 1s in each row is in $ [a, b] $.  \nLet $ S \\subseteq \\{0,1\\}^{n^2} $ be the set of all lexicographically ordered state vectors obtained by flattening matrices in $ \\mathcal{M} $ row-wise.  \n\n**Constraints**  \n1. $ |S| = \\left( \\sum_{k=a}^{b} \\binom{n}{k} \\right)^n $  \n2. For each query time $ t_i \\in \\mathbb{Z} $, $ 1 \\leq t_i \\leq 10^{18} $  \n\n**Objective**  \nFor each query $ t_i $:  \n- If $ t_i > |S| $, output \"_No such matrix._\"  \n- Else, output the $ t_i $-th lexicographically smallest matrix in $ S $, formatted as $ n $ lines of $ n $ characters (0 or 1).","simple_statement":"Given an n×n grid of 0s and 1s, valid grids must have exactly a 1s in each row and exactly b 1s in each column.  \nAll valid grids are listed in lexicographic order.  \nFor q queries, each giving a time t, output the t-th grid in this list.  \nIf t is larger than the total number of valid grids, output \"No such matrix.\"","has_page_source":false}