402846: GYM100917 M Matrix, The

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

M. Matrix, Thetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

...Neo finally understood how The Matrix is working.

The Matrix is the square grid n × n; each cell of the grid contains 0 or 1. Next additional limitations are working for The Matrix:

  • Each column contains at least one 1; ones in the column are "continuous", i.e. no zeros between any two ones in the column can be found.
  • Each line number of ones is between a and b, inclusively

The Matrix changes with time following next law: lets define 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.

Neo is sure that he can reconstruct the Matrix in any moment of time. Can you do it?

Input

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).

Output

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.

ExampleInput
3 2 3 5
1
2
16
34
35
Output
011
011
101
 
011
011
110
 
101
111
101
 
111
111
111
 
No such matrix.

加入题单

上一题 下一题 算法标签: