Binary strings are strings that can only have 0 or 1 as the characters. The hash value of a string is calculated using the formula bellow:
Where is the length of the string, is the ’th character of the string and and are two positive integers.
For example, let and , then “0010” will generate as the hash value.
Given the values of , , and , your task is to print the lexicographically smallest binary string of length that will generate as the hash value.
The input will start with an integer () — the number of test cases.
The next lines will contain 4 space separated integers , , and () each.
It is guaranteed that sum of in all the test cases does not exceed .
For each test case in a line print the lexicographically smallest binary string of length that generates as the hash value or print -1 if it doesn’t exist.
Input | Output |
---|---|
3 2 1 1 0 4 7 3 6 4 37 2 35 | 00 0010 -1 |
String is lexicographically smaller than string if it is shorter than () and is its prefix, or if none of them is a prefix of the other and at the first position where they differ, the character in is smaller than the character in .