AT_scpc2026_div2_i Sum and Difference

Terra 正在研究如何使用加法和减法变换整数对。Terra 研究的变换方法使用以下两种操作。 操作 1：$ (A, B) \rightarrow (A+B, A-B) $ 操作 2：$ (A, B) \rightarrow (B-A, A+B) $ 每一个变换过程可以根据操作的顺序表示为一个字符串。如果第 $i$ 个字符是 `1`，表示第 $i$ 步选择了操作 1；如果是 `2`，表示选择了操作 2。如果没有执行任何操作，则变换过程用空字符串表示，字符串的长度等于应用的操作次数。 Terra 想要按顺序列出所有将 $ (A, B) $ 变换成 $ (C, D) $ 的变换过程。当每一个变换过程用字符串表示时，短的字符串排在前面，长度相同的按字典序较小的排在前面。 给定测试组数量 $ T$，对于每个测试用例，给出 $ (A, B), (C, D) $ 和 $ P $。请你找出所有能把 $ (A, B) $ 变换为 $ (C, D) $ 的变换过程中第 $ P $ 个变换序列，按上述顺序排列。如果这样的第 $ P $ 个字符串不存在，输出 `-1`；如果第 $ P $ 个变换序列为空字符串，输出 `EMPTY`。

输入按以下格式从标准输入读入： > $ 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 $

对于每个测试用例，输出一行，表示将 $ (A, B) $ 变换为 $ (C, D) $ 的所有变换序列中，第 $ P $ 个序列所对应的字符串。如果这样的第 $ P $ 个字符串不存在，输出 `-1`；如果输出的是空字符串，输出 `EMPTY`。

### 样例解释 1 在第一个测试用例中，将 $ (1,0) $ 变换为 $ (1,0) $ 的最短变换方法就是不做任何操作，因此输出应该为 `EMPTY`。 在第二个测试用例中，没有任何变换可以将 $ (1,0) $ 变换为 $ (0,1) $，因此输出应为 `-1`。 ### 数据范围 - $ 1 \leq T \leq 100\,000 $ - $ -10^9 \leq A, B, C, D \leq 10^9 $ - $ 1 \leq P \leq 10^9 $ - 所有给定的数字均为整数。 由 ChatGPT 5 翻译