GUESSN5 - Guess The Number With Lies v5

GUESSN5

Judge has chosen an integer x in the range [1, n]. Your task is to find x, using at most m queries as described below. But be careful, because there are 2 important things:

1. The Judge can lie. Judge is allowed to lie w times in single game and only in reply for query.

2. You must prepare all queries at once and send all of them to the Judge before You got any reply.

Query

Single query should contains string s1s2s3...sn, where si is '0' or '1'. The reply for query is "YES", if sx = '1', or "NO" otherwise.

For example, when n=8, x=5 and query is "00101011", the Judge will reply "YES" (if telling the truth) or "NO" (if lying), because the 5th character in query is '1'.

Real task and scoring

The real task is not to find the number x chosen by Judge, but only to prepare queries, which allow You to guess the x value for every possible Judge's reply. The Judge won't give You reply for Your queries.

If the Judge will find such reply for Your queries, that there will be more than one x value possible, You will fail the test case (see example for detail explanation). Otherwise You succeed.

If You succeed, Your score is q2, where q is the number of queries, that You use. If You fail, You got penalty score equal to 4m2. Total score is the sum of scores of single games. The smaller score is the better score.

Input

The first line of input contains one integer T - the number of test cases. Then T test cases follow.

Each test case contains one line with three single-space separated integers n, w and m, where n is the size of the game, w is the maximal number of lies and m is the maximal number of queries, that You can use.

Output

For each test case print a line with one integer q - the number of queries that You want to ask.

Then print q lines with Your queries. Each query should be string of length n, with all characters '0' or '1'.

Constraints

1 ≤ T ≤ 27

2 ≤ w ≤ 24

2 ≤ n ≤ 212

(2w+1) * ⌈log2 n⌉ ≤ m

0 ≤ q ≤ m

Example

Input:
4
2 2 6
2 3 8
2 16 34
5 2 18

One of possible output is:
6
01
01
01
01
01
01
6
01
01
01
01
01
01
0
15
00011
00011
00011
00011
00011
01010
01010
01010
01010
01010
00100
00101
00110
01100
01111

Explanation:

Notation: reply "YYN..." means, that Judge replied "YES" for first and second query, "NO" for third query, and so on...

In 1st test case there are only two numbers. Judge can reply "YYYYYY", "NNNNNN" (without lie), "YYYYYN", "YYYYNY", "YYYNYY", "YYNYYY", "YNYYYY", "NYYYYY", "NNNNNY", "NNNNYN", "NNNYNN", "NNYNNN", "NYNNNN", "YNNNNN", (with one lie) or "NNNNYY", "NNNYNY", "NNNYYN", "NNYNNY", "NNYNYN", "NNYYNN", "NYNNNY", "NYNNYN", "NYNYNN", "NYYNNN", "YNNNNY", "YNNNYN", "YNNYNN", "YNYNNN", "YYNNNN", "NNYYYY", "NYNYYY", "NYYNYY", "NYYYNY", "NYYYYN", "YNNYYY", "YNYNYY", "YNYYNY", "YNYYYN", "YYNNYY", "YYNYNY", "YYNYYN", "YYYNNY", "YYYNYN", "YYYYNN" (with 2 lies). The other replies ("NNNYYY", "NNYNYY", "NNYYNY", "NNYYYN", "NYNNYY", "NYNYNY", "NYNYYN", "NYYNNY", "NYYNYN", "NYYYNN", "YNNNYY", "YNNYNY", "YNNYYN", "YNYNNY", "YNYNYN", "YNYYNN", "YYNNNY", "YYNNYN", "YYNYNN", "YYYNNN") are not ok, because for every of them and for every possible x value, the Judge lies more than two times. For each good reply, there is only one integer from range [1, 2], that match this replies ("match" means match all except at most two of queries). The score is 62 = 36. Notice, that You can use the same query more than once.

In 2nd test case player tried to give the solution, but the solution is wrong. The Judge can reply for example "YYYNNN" and then for both possible values of x the judge lied 3 times. Player needs more queries in this case. The score is penalty score 4 * 82 = 256.

In 3rd test case player decided to skip. Player got the penalty score 4 * 342 = 4624.

In 4th test case the nubmer of queries given by player is smaller than the maximal possible number. For every possible Judge's reply there is only one possible value of x, so test succeeded. The score is 152 = 225.

Total score is 36 + 256 + 4624 + 225 = 5141.

Similar problems

There is a family of similar problems. Here is the table with them:

CodeNumber of liesQuery formatTypeSectionDifficulty
GUESSN1 1 subset interactive challenge easy
GUESSN2 2-16 subset interactive challenge medium/hard
GUESSN3 1 range interactive classical medium
GUESSN4 1 subset non-interactive challenge medium
GUESSN5 2-16 subset non-interactive challenge hard

subset - the query is about any subset of {1,2,...,n}
range - the query is about any range [a,b]
 interactive - the Judge replies after every query
non-interactive - all queries have to be asked at once, before any reply


Added by:miodziu
Date:2013-12-29
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-01-03 16:09:21 Hoàng Vãn Hiếu
Bài này khó quá trời
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.