#line 2 "ProCon/Library/template/util.hpp" #include #include #include #include #include #include #include #include #include #include #include #include #include using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; constexpr i8 operator""_i8(unsigned long long n) noexcept { return static_cast(n); } constexpr i16 operator""_i16(unsigned long long n) noexcept { return static_cast(n); } constexpr i32 operator""_i32(unsigned long long n) noexcept { return static_cast(n); } constexpr i64 operator""_i64(unsigned long long n) noexcept { return static_cast(n); } constexpr u8 operator""_u8(unsigned long long n) noexcept { return static_cast(n); } constexpr u16 operator""_u16(unsigned long long n) noexcept { return static_cast(n); } constexpr u32 operator""_u32(unsigned long long n) noexcept { return static_cast(n); } constexpr u64 operator""_u64(unsigned long long n) noexcept { return static_cast(n); } constexpr char eoln = '\n'; template constexpr T infty = std::numeric_limits::max() / Div - 2; template using RevPriorityQueue = std::priority_queue, std::greater>; constexpr std::array, 4> dxy4 = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}; constexpr std::array infty_list = {infty, infty, infty, infty, infty, infty}; template bool is_infty(const T v) { if (v > 0 and static_cast(v) > infty) return false; for (const auto e : infty_list) { if (e == static_cast(v)) return true; } return false; } class Range { struct Iterator { int itr; constexpr Iterator(const int pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iterator &other) const noexcept { return itr != other.itr; } constexpr int operator*() const noexcept { return itr; } }; const Iterator first, last; public: explicit constexpr Range(const int f, const int l) noexcept : first(f), last(std::max(f, l)) {} constexpr Iterator begin() const noexcept { return first; } constexpr Iterator end() const noexcept { return last; } }; class ReversedRange { struct Iterator { int itr; constexpr Iterator(const int pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { --itr; } constexpr bool operator!=(const Iterator &other) const noexcept { return itr != other.itr; } constexpr int operator*() const noexcept { return itr; } }; const Iterator first, last; public: explicit constexpr ReversedRange(const int f, const int l) noexcept : first(l - 1), last(std::min(f, l) - 1) {} constexpr Iterator begin() const noexcept { return first; } constexpr Iterator end() const noexcept { return last; } }; #define SIKICM_REP1(i, r) for (const int i : Range(0, r)) #define SIKICM_REP2(i, l, r) for (int i : Range(l, r)) #define SIKICM_RVP1(i, r) for (const int i : ReversedRange(0, r)) #define SIKICM_RVP2(i, l, r) for (int i : ReversedRange(l, r)) #define SIKICM_SELECT2(a, b, c, name, ...) name #define REP(...) SIKICM_SELECT2(__VA_ARGS__, SIKICM_REP2, SIKICM_REP1)(__VA_ARGS__) #define RVP(...) SIKICM_SELECT2(__VA_ARGS__, SIKICM_RVP2, SIKICM_RVP1)(__VA_ARGS__) #define HRL(n) for ([[maybe_unused]] const int loop_counter : Range(0, n)) template constexpr int len(const Container &c) { return static_cast(std::size(c)); } template constexpr bool chmin(T &v, const T a) { if (v > a) { v = a; return true; } return false; } template constexpr bool chmax(T &v, const T a) { if (v < a) { v = a; return true; } return false; } template constexpr T ceil_div(const T x, const T y) { assert(y != 0); assert(x > 0 and y > 0); return (x + y - 1) / y; } template constexpr int lwb(const Container &c, const T &val) { return static_cast(std::distance(c.cbegin(), std::lower_bound(c.cbegin(), c.cend(), val))); } template constexpr int upb(const Container &c, const T &val) { return static_cast(std::distance(c.cbegin(), std::upper_bound(c.cbegin(), c.cend(), val))); } template constexpr int lmp(const Container &c, const F &f) { return static_cast( std::distance(c.cbegin(), std::partition_point(c.cbegin(), c.cend(), f))); } template auto make_vec(const int n, const T &value) { return std::vector(n, value); } template auto make_vec(const int n, Args... args) { return std::vector(n, make_vec(args...)); } template void renumber(const std::vector &order, std::vector &head, Tail &... tail) { const int n = len(order); std::vector sorted_head(n); REP(i, n) sorted_head[i] = head[order[i]]; head = std::move(sorted_head); if constexpr (sizeof...(Tail) != 0) { renumber(order, tail...); } } template std::vector priority_sort(std::vector &head, std::vector &... tail) { const int n = len(head); std::vector> res(n); REP(i, n) res[i] = std::make_tuple(head[i], tail[i]..., i); std::sort(res.begin(), res.end()); std::vector order(n); REP(i, 0, n) order[i] = std::get>>(res[i]); renumber(order, head, tail...); return order; } std::vector iotav(const int n) { std::vector ret(n); std::iota(ret.begin(), ret.end(), 0); return ret; } template auto calc_sum(const Container &c) { return std::accumulate(c.cbegin(), c.cend(), static_cast(0)); } template constexpr T ceil_log2(const T x) { int e = 0; while ((static_cast(1) << e) < x) ++e; return e; } template constexpr int ceil_pow2(const T x) { return 1 << ceil_log2(x); } #line 5 "ProCon/Library/template/debug.hpp" #include namespace DebugImpl { template struct is_specialize : std::false_type {}; template struct is_specialize::type> : std::true_type {}; template struct is_specialize::type> : std::true_type {}; template struct is_specialize::value, void>> : std::true_type {}; void dump(const char &t) { std::cerr << t; } void dump(const std::string &t) { std::cerr << t; } void dump(const bool &t) { std::cerr << (t ? "true" : "false"); } template ::value, std::nullptr_t> = nullptr> void dump(const U &t) { std::cerr << t; } template void dump(const T &t, std::enable_if_t::value> * = nullptr) { std::string res; if (is_infty(t)) res = "inf"; if constexpr (std::is_signed::value) { if (is_infty(-t)) res = "-inf"; } if (res.empty()) res = std::to_string(t); std::cerr << res; } template void dump(const std::pair &); template void dump(const std::pair &); template void dump(const T &t, std::enable_if_t::value> * = nullptr) { std::cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); std::cerr << (++it == t.end() ? "" : ", "); } std::cerr << " ]"; } template void dump(const std::pair &t) { std::cerr << "( "; dump(t.first); std::cerr << ", "; dump(t.second); std::cerr << " )"; } template void dump(const std::pair &t) { std::cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); std::cerr << (i == t.second - 1 ? "" : ", "); } std::cerr << " ]"; } void trace() { std::cerr << std::endl; } template void trace(Head &&head, Tail &&... tail) { std::cerr << " "; dump(head); if (sizeof...(tail) != 0) std::cerr << ','; trace(std::forward(tail)...); } } // namespace DebugImpl #ifdef SIKI_DEBUG #define vpr(...) \ do { \ std::cerr << "## " << #__VA_ARGS__ << " ="; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define vpr(...) (void(0)) #endif // https://github.com/NyaanNyaan/library/blob/master/template/debug.hpp #line 2 "ProCon/Library/template/macro.hpp" #define ALL(x) (x).begin(), (x).end() #define pf push_front #define pb push_back #define ef emplace_front #define eb emplace_back #define ppf pop_front #define ppb pop_back #line 4 "main.cpp" #include using namespace std; #line 2 "ProCon/Library/nyaan_lib/modint/modint.hpp" template struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt &operator+=(const ModInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt(t); return (is); } int get() const { return x; } static constexpr int get_mod() { return mod; } }; #line 9 "main.cpp" using Fp = ModInt<998244353>; int main() { int T; cin >> T; while (T--) { int N; cin >> N; vector ans(N, -1); REP(q, 10) { vector split; REP(i, N) if (ans[i] != -1) split.push_back(i); split.push_back(N); cout << '?'; vector qu(N - 1); int now = 0; REP(i, N - 1) { if (i == 0) { qu[i] = q % 2 == 0; if (split.size() > now and split[now] == i) ++now; } else { if (split.size() > now and split[now] == i) { ++now; qu[i] = q % 2 == 0; } else { qu[i] = !qu[i - 1]; } } } REP(i, N - 1) cout << ' ' << qu[i]; cout << endl; vector B(N); REP(i, N) cin >> B[i]; ans[0] = B[0]; REP(i, 1, N) { if (ans[i] == -1) { if (B[i - 1] != B[i]) { ans[i] = B[i]; } } } } cout << '!'; for (const int e : ans) cout << ' ' << e; cout << endl; } }