AT_scpc2026_div2_i Sum and Difference

#### 表示言語 / / テラは和と差を用いて整数の組を変換する方法について研究している．テラが研究している変換方法では，次の $ 2 $ つの操作を使う． 操作 1: $ (A, B) \rightarrow (A+B, A-B) $ 操作 2: $ (A, B) \rightarrow (B-A, A+B) $ 各変換過程は，操作を使用した順序に従って文字列で表すことができる． $ i $ 文字目が `1` なら $ i $ 番目の操作として操作 1 を，`2` なら操作 2 を選んだことを表す．操作を一度も行わない変換過程は空文字列で表され，文字列の長さは適用した操作の回数に等しい． テラは $ (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 $ 番目に来る変換過程の文字列を $ 1 $ 行に出力せよ． $ P $ 番目の文字列が存在しないなら `-1`， $ P $ 番目に来る変換過程の文字列が空文字列なら `EMPTY` を出力せよ．

### Sample Explanation 1 1 番目のテストケースでは， $ (1,0) $ を $ (1,0) $ にする最短の変換は何もしないことであるため，`EMPTY` を出力する必要がある． 2 番目のテストケースでは， $ (1,0) $ を $ (0,1) $ にする変換が存在しないため，`-1` を出力する必要がある． ### Constraints - $ 1 \leq T \leq 100\,000 $ - $ -10^9 \leq A, B, C, D \leq 10^9 $ - $ 1 \leq P \leq 10^9 $ - 入力される数値はすべて整数である．