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.

特拉正在研究如何使用加法和减法来变换整数对。特拉所研究的变换方法包含以下两种操作：

操作 1：$(A, B) \rightarrow (A+B, A-B)$
操作 2：$(A, B) \rightarrow (B-A, A+B)$

每种变换过程均可按所用操作的顺序表示为一个字符串：若第 $i$ 个字符为 1，表示第 $i$ 次执行的是操作 1；若为 2，则表示第 $i$ 次执行的是操作 2。未执行任何操作的变换过程用空字符串表示，且该字符串的长度等于所应用的操作次数。

特拉希望按顺序列出所有能将 $(A, B)$ 变换为 $(C, D)$ 的变换过程。当每个变换过程被表示为字符串时，较短的字符串排在前面；长度相同时，字典序较小的字符串排在前面。

给定测试用例数量 $T$，对每个测试用例，输入 $(A, B)$、$(C, D)$ 和 $P$。请找出所有能将 $(A, B)$ 变换为 $(C, D)$ 的变换过程中，按上述顺序排列的第 $P$ 个变换过程所对应的字符串。若不存在第 $P$ 个字符串，则输出 -1；若第 $P$ 个字符串为空字符串，则输出 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$

输入从标准输入中以如下格式给出：

$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.

对于每个测试用例，输出一行，包含将 $(A, B)$ 变换为 $(C, D)$ 的所有变换过程按顺序排列时的第 $P$ 个变换过程所对应的字符串。如果不存在第 $P$ 个字符串，则输出 -1；如果第 $P$ 个变换过程对应空字符串，则输出 EMPTY。

表示言語

/ /

Sample 1 Explanation:
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.

表示语言

/ /

样例 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$
• 所有给定的数均为整数。