AT_scpc2026_div2_i Sum and Difference

#### 表示言語 / / Terra is studying how to transform pairs of integers using sums and differences. The transformation method Terra is studying uses the following two operations. Operation 1: $ (A, B) \rightarrow (A+B, A-B) $ Operation 2: $ (A, B) \rightarrow (B-A, A+B) $ Each transformation process can be represented as a string according to the order in which the operations are used. If the $ i $ -th character is `1`, operation 1 was chosen as the $ i $ -th operation; if it is `2`, operation 2 was chosen. A transformation process in which no operation is performed is represented by the empty string, and the length of the string is equal to the number of operations applied. Terra wants to list all transformation processes that turn $ (A, B) $ into $ (C, D) $ in order. When each transformation process is represented as a string, strings of shorter length come first, and among strings of the same length, lexicographically smaller strings come first. The number of test cases $ T $ is given, and for each test case, $ (A, B) $ , $ (C, D) $ , and $ P $ are given. Find the string of the $ P $ -th transformation process in this order among the transformation processes that turn $ (A, B) $ into $ (C, D) $ . If the $ P $ -th string does not exist in this order, output `-1`; if the $ P $ -th string is the empty string, output `EMPTY`.

The input is given from Standard Input in the following format: > $ T $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ P_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ D_2 $ $ P_2 $ $ \vdots $ $ A_T $ $ B_T $ $ C_T $ $ D_T $ $ P_T $

For each test case, output one line containing the string of the $ P $ -th transformation process when the transformations that turn $ (A, B) $ into $ (C, D) $ are listed in order. If the $ P $ -th string does not exist, output `-1`; if the $ P $ -th transformation process is represented by the empty string, output `EMPTY`.

### Sample Explanation 1 In the first test case, the shortest transformation that turns $ (1,0) $ into $ (1,0) $ is to do nothing, so `EMPTY` should be output. In the second test case, there is no transformation that turns $ (1,0) $ into $ (0,1) $ , so `-1` should be output. ### Constraints - $ 1 \leq T \leq 100\,000 $ - $ -10^9 \leq A, B, C, D \leq 10^9 $ - $ 1 \leq P \leq 10^9 $ - All given numbers are integers.