Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Reverse Hash

By curly_braces · Limits 1s, 512 MB

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:

$\sum_{i=1}^{n} s_i * b^i \mod m$

Where $n$ is the length of the string, $s_i$ is the $i$’th character of the string and $b$ and $m$ are two positive integers.

For example, let $b=3$ and $m=7$, then “0010” will generate $(0*3^1+0*3^2+1*3^3+0*3^4 ) \mod 7= 27 \mod 7 = 6$ as the hash value.

Given the values of $n$, $m$, $b$ and $h$, your task is to print the lexicographically smallest binary string of length $n$ that will generate $h$ as the hash value.

Input

The input will start with an integer $T(1 \leq T \leq 10^5)$ — the number of test cases.

The next $T$ lines will contain 4 space separated integers $n$, $m$, $b$ and $h$ $(1 \leq n,m,b \leq 10^3; 0 \leq h < m)$ each.

It is guaranteed that sum of $n$ in all the test cases does not exceed $10^5$.

Output

For each test case in a line print the lexicographically smallest binary string of length $n$ that generates $h$ as the hash value or print -1 if it doesn’t exist.

Sample

InputOutput
3
2 1 1 0
4 7 3 6
4 37 2 35

00
0010
-1


String $A$ is lexicographically smaller than string $B$  if it is shorter than $B (|A| < |B|)$ 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 $A$ is smaller than the character in $B$.

Statistics

78% Solution Ratio

Wojciech.324122Earliest, 2M ago

flukehn.841988Fastest, 0.0s

ArcturusLightest, 393 kB

Xi.498579Shortest, 779B