CF1835A k-th equality

Consider all equalities of form $ a + b = c $ , where $ a $ has $ A $ digits, $ b $ has $ B $ digits, and $ c $ has $ C $ digits. All the numbers are positive integers and are written without leading zeroes. Find the $ k $ -th lexicographically smallest equality when written as a string like above or determine that it does not exist. For example, the first three equalities satisfying $ A = 1 $ , $ B = 1 $ , $ C = 2 $ are - $ 1 + 9 = 10 $ , - $ 2 + 8 = 10 $ , - $ 2 + 9 = 11 $ . An equality $ s $ is lexicographically smaller than an equality $ t $ with the same lengths of the numbers if and only if the following holds: - in the first position where $ s $ and $ t $ differ, the equality $ s $ has a smaller digit than the corresponding digit in $ t $ .

Each test contains multiple test cases. The first line of input contains a single integer $ t $ ( $ 1 \leq t \leq 10^3 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains integers $ A $ , $ B $ , $ C $ , $ k $ ( $ 1 \leq A, B, C \leq 6 $ , $ 1 \leq k \leq 10^{12} $ ). Each input file has at most $ 5 $ test cases which do not satisfy $ A, B, C \leq 3 $ .

For each test case, if there are strictly less than $ k $ valid equalities, output $ -1 $ . Otherwise, output the $ k $ -th equality as a string of form $ a + b = c $ .

In the first test case, the first $ 9 $ solutions are: $ \langle 1, 1, 2 \rangle, \langle 1, 2, 3 \rangle, \langle 1, 3, 4 \rangle, \langle 1, 4, 5 \rangle, \langle 1, 5, 6 \rangle, \langle 1, 6, 7 \rangle, \langle 1, 7, 8 \rangle, \langle 1, 8, 9 \rangle, \langle 2, 1, 3 \rangle $ . Int the third test case, there are no solutions as the smallest possible values for $ a $ and $ b $ are larger than the maximal possible value of $ c $ — $ 10 + 10 = 20 > 9 $ . Please note that whitespaces in the output matter.