Both operations double the sum of squares:

\[ (A+B)^2+(A-B)^2=2(A^2+B^2), \]

and

\[ (B-A)^2+(A+B)^2=2(A^2+B^2). \]

Therefore, after applying a string of length \(k\), we must have

\[ C^2+D^2=2^k(A^2+B^2). \]

First, consider the case \((A,B)\ne(0,0)\). Then the length of a valid string is uniquely determined, if it exists. In other words,

\[ \frac{C^2+D^2}{A^2+B^2} \]

must be a power of two, and its exponent becomes the length \(k\). If this condition is not satisfied, the answer is immediately -1.

Now suppose the length \(k\) is fixed.

Even after composing the two operations many times, the result has only four possible directions, up to scaling. For example, if \(k\) is even, the result must be one of

\[ (A,B),\quad (-B,A),\quad (-A,-B),\quad (B,-A), \]

multiplied by \(2^{k/2}\).

If \(k\) is odd, one more operation is applied after such a form. Thus, the possible forms are

\[ \begin{aligned} &(A+B,A-B),\quad (B-A,A+B),\\ &(-A-B,-A+B),\quad (A-B,-A-B), \end{aligned} \]

multiplied by \(2^{(k-1)/2}\).

Let \(dp[i][s]\) be the number of strings of length \(i\) whose result belongs to state \(s\), where \(s\) is one of the four directions above.

Initially, only the empty string exists, so

\[ dp[0][0]=1. \]

When we append one character, the state changes according to which operation is applied. Since there are only four states and two operations, all transitions can be precomputed.

Using this DP, define

\[ \operatorname{cnt}(r,X,Y,C,D) \]

as the number of strings of length \(r\) that transform the current value \((X,Y)\) into \((C,D)\).

Since there are only four possible final forms, we simply check which of the four states matches \((C,D)\). If it matches state \(s\), the answer is \(dp[r][s]\); otherwise, it is \(0\).

Now we restore the \(P\)-th string in lexicographic order.

Suppose the current value is \((X,Y)\), and the remaining length is \(r\). First, assume that the next character is 1, and count how many completions are possible. If this count is at least \(P\), we choose 1. Otherwise, we subtract this count from \(P\) and choose 2.

Repeating this process until the length becomes \(0\) gives the desired string. If the total number of valid strings is smaller than \(P\), the answer is -1. If the valid string has length \(0\), output EMPTY.

It remains to handle the case \((A,B)=(0,0)\) separately.

If we start from \((0,0)\), both operations always keep the value equal to \((0,0)\). Therefore, if \((C,D)\ne(0,0)\), the answer is -1.

Otherwise, every string is valid. Thus, the problem becomes finding the \(P\)-th string over 1 and 2 when all strings are listed by increasing length, and then lexicographic order inside the same length.

The number of strings before length \(L\) is

\[ 1+2+\cdots+2^{L-1}=2^L-1. \]

So we find the length \(L\) such that \(P\) belongs to the block of strings of length \(L\), and then interpret its order inside the block as a binary number, where 1 corresponds to \(0\) and 2 corresponds to \(1\).

For each query, the time complexity is

\[ {\cal O}(\log P+\log |C^2+D^2|). \]

Therefore, the total time complexity is

\[ {\cal O}(Q(\log P+\log |C^2+D^2|)). \]