Reverse Hash

curly_braces Criterion 2022 Round 15
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:

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

Where nn is the length of the string, sis_i is the ii’th character of the string and bb and mm are two positive integers.

For example, let b=3b=3 and m=7m=7, then “0010” will generate (031+032+133+034)mod7=27mod7=6(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 nn, mm, bb and hh, your task is to print the lexicographically smallest binary string of length nn that will generate hh as the hash value.

Input

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

The next TT lines will contain 4 space separated integers nn, mm, bb and hh (1n,m,b103;0h<m1 \leq n,m,b \leq 10^3; 0 \leq h < m) each.

It is guaranteed that sum of nn in all the test cases does not exceed 10510^5.

Output

For each test case in a line print the lexicographically smallest binary string of length nn that generates hh 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 AA is lexicographically smaller than string BB  if it is shorter than BB (A<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 AA is smaller than the character in BB.

Submit

Login to submit.

Statistics

72% Solution Ratio
Wojciech.324122Earliest, 7M ago
flukehn.841988Fastest, 0.0s
ArcturusLightest, 393 kB
Xi.498579Shortest, 779B
Toph uses cookies. By continuing you agree to our Cookie Policy.