AT_xmascon22_g Generator SAT

$ 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 $ の値を入れ替える． ```cpp #include std::vector Generate(int N, long long S) { long long s = S; std::vector 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 $ 行目にテストケースの個数 $ T $ が与えられる．その後， $ T $ 個のテストケースがそれぞれ以下の形式で与えられる． > $ N $ $ S $

各テストケースについて，以下のように $ 1 $ 行で出力せよ． 条件を満たすことができる場合，良い整数の決め方を $ 1 $ 通り選び，以下のような長さ $ N $ の文字列を出力せよ：各 $ j = 1, 2, \ldots, N $ に対し， - $ +j $ が良い整数の場合， $ j $ 文字目は `+` である． - $ -j $ が良い整数の場合， $ j $ 文字目は `-` である． 条件を満たすことができない場合，`0` と出力せよ．

### Sample Explanation 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 $ を良い整数と決めれば条件を満たす． ### Constraints - $ 1 \le T \le 10 $ ． - $ 1 \le N \le 10^5 $ ． - $ 0 \le S < 998244353 $ ．