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:

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 T(1T105)T(1 \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<m)(1 \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 B (A<B)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.

Discussion

Statistics


78% Solution Ratio

Wojciech.324122Earliest, 2M ago

flukehn.841988Fastest, 0.0s

ArcturusLightest, 393 kB

Xi.498579Shortest, 779B

Submit

Login to submit

Editorial

As it is a binary string, the hash value of a string will be the sum of some distinct power of base ...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.