問題文

1 個の入力ファイルにつき T 個のテストケースが与えられる．各テストケースで整数 N, S が与えられるので，以下の問に答えよ．

整数 A_0, A_1, \ldots, A_{4N-1} を以下のように定める．数式および C++ コード片で示す：

1. 変数 s を s \gets S とする．
2. i = 0, 1, \ldots, 4 N - 1 に対しこの順で，A_i \gets \lfloor i/4 \rfloor + 1 とする．
3. i = 0, 1, \ldots, 4 N - 1 に対しこの順で，s \gets (s \times 2022) \bmod 998244353 としてから，s \not\equiv 0 \pmod{2} ならば A_i \gets -A_i とする．
4. i = 0, 1, \ldots, 4 N - 1 に対しこの順で，s \gets (s \times 2022) \bmod 998244353 としてから，A_{s \bmod (i+1)} と A_i の値を入れ替える．

#include <vector>
std::vector<int> Generate(int N, long long S) {
  long long s = S;
  std::vector<int> A(4 * N);
  for (int i = 0; i < 4 * N; ++i) {
    A[i] = i / 4 + 1;
  }
  for (int i = 0; i < 4 * N; ++i) {
    s = (s * 2022) % 998244353;
    if (s % 2 != 0) {
      A[i] = -A[i];
    }
  }
  for (int i = 0; i < 4 * N; ++i) {
    s = (s * 2022) % 998244353;
    int j = s % (i + 1);
    int t = A[j];
    A[j] = A[i];
    A[i] = t;
  }
  return A;
}

各 j = 1, 2, \ldots, N に対して +j と -j のいずれかちょうど一方を「良い整数」と決める方法 2^N 通りのうち，以下の N 個の条件をすべて満たすものが存在するかどうか判定し，存在する場合はそのような方法を 1 通り求めよ：

• A_0, A_1, A_2, A_3 のうち少なくとも 1 個は良い整数である．
• A_4, A_5, A_6, A_7 のうち少なくとも 1 個は良い整数である．
• \cdots
• A_{4N-4}, A_{4N-3}, A_{4N-2}, A_{4N-1} のうち少なくとも 1 個は良い整数である．

制約

• 1 \le T \le 10．
• 1 \le N \le 10^5．
• 0 \le S < 998244353．

入力例 1

2
3 1
4 20221224

出力例 1

++-
+--+

1 個目のテストケースでは，

• (A_0, A_1, A_2, A_3) = (-3, -3, -2, +3)
• (A_4, A_5, A_6, A_7) = (+2, +1, -1, +3)
• (A_8, A_9, A_{10}, A_{11}) = (+2, +1, -2, +1)

となる．例えば，+1, +2, -3 を良い整数と決めれば条件を満たす．

2 個目のテストケースでは，

• (A_0, A_1, A_2, A_3) = (+3, -2, +2, -3)
• (A_4, A_5, A_6, A_7) = (+4, +1, +3, -1)
• (A_8, A_9, A_{10}, A_{11}) = (+4, +2, +1, +4)
• (A_{12}, A_{13}, A_{14}, A_{15}) = (-1, -2, -3, -4)

となる．例えば，+1, -2, -3, +4 を良い整数と決めれば条件を満たす．