M. XORzocity
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given constant positive integers $$$k$$$, $$$x$$$, and $$$y$$$. An array $$$a$$$ of size $$$n \gt k$$$ is defined such that:

$$$$$$a_i = \begin{cases} 2^{i-1} & 1 \le i \le k\\ a_{i-x} \oplus a_{i-y} & k \lt i \le n \end{cases}$$$$$$

Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Your task is to print the binary representation of $$$a_n$$$.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line of each test case contains four integers $$$n$$$, $$$k$$$, $$$x$$$, and $$$y$$$ ($$$2 \le n \le 10^{18}$$$, $$$1 \le k \le \min(10^6, n - 1)$$$, $$$1 \le x, y \le k$$$) — the size of the array and the constants described above, respectively.

It is guaranteed that the sum of $$$k$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a binary string of length $$$k$$$ — the binary representation of $$$a_n$$$, with digits in order from most to least significant.

Formally, the $$$i$$$-th character of the string should be 1 if the $$$2^{k-i}$$$ bit of $$$a_n$$$ is set and 0 otherwise.

Example
Input
7
10 6 3 5
123456 1 1 1
2000 7 1 2
12581674 5 5 2
3523686 10 8 8
123456789123456789 8 4 7
500000000000000000 13 11 8
Output
011010
0
1100000
10101
0000000000
00011000
0100001011000
Note

In the first test case, the array $$$a$$$ is $$$[1, 2, 4, 8, 16, 32, 10, 20, 40, 26]$$$. Since $$$26_{10} = 011010_2$$$, we print $$$011010$$$.

In the second test case, the array $$$a$$$ is $$$[1, 0, 0, \cdots 0]$$$.

In the third test case, the array $$$a$$$ is $$$[1, 2, 4, 8, 16, 32, 64, 96, 32, 64, 96, \cdots 32, 64, 96]$$$.