// BEGIN: main.cpp #line 1 "main.cpp" // BEGIN: my_template.hpp #line 1 "my_template.hpp" #if defined(LOCAL) #include #else #if defined(__GNUC__) #include #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,popcnt") #endif #include using namespace std; using ll = long long; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using f128 = __float128; template constexpr T infty = 0; template <> constexpr int infty = 1'010'000'000; template <> constexpr ll infty = 2'020'000'000'000'000'000; template <> constexpr u32 infty = infty; template <> constexpr u64 infty = infty; template <> constexpr i128 infty = i128(infty) * 2'000'000'000'000'000'000; template <> constexpr double infty = numeric_limits::infinity(); template <> constexpr long double infty = numeric_limits::infinity(); using pi = pair; using vi = vector; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using pq_max = priority_queue; template using pq_min = priority_queue, greater>; #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) // https://trap.jp/post/1224/ #define FOR1(a) for (ll _ = 0; _ < ll(a); ++_) #define FOR2(i, a) for (ll i = 0; i < ll(a); ++i) #define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i) #define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c)) #define FOR1_R(a) for (ll i = (a) - 1; i >= ll(0); --i) #define FOR2_R(i, a) for (ll i = (a) - 1; i >= ll(0); --i) #define FOR3_R(i, a, b) for (ll i = (b) - 1; i >= ll(a); --i) #define overload4(a, b, c, d, e, ...) e #define overload3(a, b, c, d, ...) d #define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__) #define all(x) (x).begin(), (x).end() #define len(x) ll(x.size()) #define elif else if #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second #define stoi stoll int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); } int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); } int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template T kth_bit(int k) { return T(1) << k; } template bool has_kth_bit(T x, int k) { return x >> k & 1; } template struct all_bit { struct iter { UINT s; iter(UINT s) : s(s) {} int operator*() const { return lowbit(s); } iter &operator++() { s &= s - 1; return *this; } bool operator!=(const iter) const { return s != 0; } }; UINT s; all_bit(UINT s) : s(s) {} iter begin() const { return iter(s); } iter end() const { return iter(0); } }; template struct all_subset { static_assert(is_unsigned::value); struct iter { UINT s, t; bool ed; iter(UINT s) : s(s), t(s), ed(0) {} UINT operator*() const { return s ^ t; } iter &operator++() { (t == 0 ? ed = 1 : t = (t - 1) & s); return *this; } bool operator!=(const iter) const { return !ed; } }; UINT s; all_subset(UINT s) : s(s) {} iter begin() const { return iter(s); } iter end() const { return iter(0); } }; template T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); } template T ceil(T x, T y) { return floor(x + y - 1, y); } template T bmod(T x, T y) { return x - y * floor(x, y); } template pair divmod(T x, T y) { T q = floor(x, y); return {q, x - q * y}; } constexpr ll TEN[] = { 1LL, 10LL, 100LL, 1000LL, 10000LL, 100000LL, 1000000LL, 10000000LL, 100000000LL, 1000000000LL, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL, 1000000000000000000LL, }; template T SUM(const U &A) { return std::accumulate(A.begin(), A.end(), T{}); } #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) template inline long long LB(const C &c, const T &x) { return lower_bound(c.begin(), c.end(), x) - c.begin(); } template inline long long UB(const C &c, const T &x) { return upper_bound(c.begin(), c.end(), x) - c.begin(); } #define UNIQUE(x) \ sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit() template T POP(deque &que) { T a = que.front(); que.pop_front(); return a; } template T POP(priority_queue &que) { T a = que.top(); que.pop(); return a; } template T POP(vc &que) { T a = que.back(); que.pop_back(); return a; } template ll binary_search(F check, ll ok, ll ng, bool check_ok = true) { if (check_ok) assert(check(ok)); while (llabs(ok - ng) > 1) { auto x = (ng + ok) / 2; (check(x) ? ok : ng) = x; } return ok; } template double binary_search_real(F check, double ok, double ng, int iter = 100) { FOR(iter) { double x = (ok + ng) / 2; (check(x) ? ok : ng) = x; } return (ok + ng) / 2; } template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } // ? は -1 vc s_to_vi(const string &S, char first_char) { vc A(S.size()); FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); } return A; } template vc cumsum(const vc &A, int off = 1) { int N = A.size(); vc B(N + 1); FOR(i, N) { B[i + 1] = B[i] + A[i]; } if (off == 0) B.erase(B.begin()); return B; } // stable sort template vc argsort(const vc &A) { vc ids(len(A)); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); }); return ids; } // A[I[0]], A[I[1]], ... template vc rearrange(const vc &A, const vc &I) { vc B(len(I)); FOR(i, len(I)) B[i] = A[I[i]]; return B; } template void concat(vc &first, const Vectors &...others) { vc &res = first; (res.insert(res.end(), others.begin(), others.end()), ...); } #endif // END: my_template.hpp #line 2 "main.cpp" // BEGIN: other/io2.hpp #line 1 "other/io2.hpp" #define INT(...) \ int __VA_ARGS__; \ IN(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ IN(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ IN(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ IN(__VA_ARGS__) #define DBL(...) \ long double __VA_ARGS__; \ IN(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ read(name) #define VV(type, name, h, w) \ vector> name(h, vector(w)); \ read(name) void read(int &a) { cin >> a; } void read(long long &a) { cin >> a; } void read(char &a) { cin >> a; } void read(double &a) { cin >> a; } void read(long double &a) { cin >> a; } void read(string &a) { cin >> a; } template void read(pair &p) { read(p.first), read(p.second); } template void read(vector &a) { for (auto &i : a) read(i); } template void read(T &a) { cin >> a; } void IN() {} template void IN(Head &head, Tail &...tail) { read(head); IN(tail...); } template ostream &operator<<(ostream &os, const pair &A) { os << A.fi << " " << A.se; return os; } template ostream &operator<<(ostream &os, const vector &A) { for (size_t i = 0; i < A.size(); i++) { if (i) os << " "; os << A[i]; } return os; } class CoutInitializer { public: CoutInitializer() { std::cout << std::defaultfloat << std::setprecision(15); } }; static CoutInitializer cout_initializer; void print() { cout << "\n"; cout.flush(); } template void print(Head &&head, Tail &&...tail) { cout << head; if (sizeof...(Tail)) cout << " "; print(forward(tail)...); } #if defined(LOCAL) template inline void _show_pack(const char *func, int line, const char *names, Ts &&...args) { // [DEBUG] solve:123 のように先頭に出す cout << "[DEBUG " << func << ':' << line << "] "; const char *p = names; bool first = true; auto next_token = [&]() -> std::pair { while (*p == ' ' || *p == ',') ++p; const char *l = p; while (*p && *p != ',') ++p; const char *r = p; return {l, r}; }; ( [&] { auto [l, r] = next_token(); while (r > l && r[-1] == ' ') --r; if (!first) cout << ' '; first = false; std::string name(l, r); cout << name << " = " << args; }(), ...); print(); } #define SHOW(...) _show_pack(__func__, __LINE__, #__VA_ARGS__, __VA_ARGS__) #else #define SHOW(...) #endif void YES(bool t = 1) { print(t ? "YES" : "NO"); } void NO(bool t = 1) { YES(!t); } void Yes(bool t = 1) { print(t ? "Yes" : "No"); } void No(bool t = 1) { Yes(!t); } void yes(bool t = 1) { print(t ? "yes" : "no"); } void no(bool t = 1) { yes(!t); } // END: other/io2.hpp #line 3 "main.cpp" // BEGIN: string/is_subseq.hpp #line 1 "string/is_subseq.hpp" template bool is_subseq(STRING& S, STRING& T) { ll p = 0; for (auto&& s: S) { while (p < len(T) && T[p] != s) ++p; if (p == len(T)) return false; ++p; } return true; }// END: string/is_subseq.hpp #line 5 "main.cpp" // BEGIN: random/base.hpp #line 1 "random/base.hpp" u64 RNG_64() { static u64 x_ = u64(chrono::duration_cast(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL; x_ ^= x_ << 7; return x_ ^= x_ >> 9; } u64 RNG(u64 lim) { return RNG_64() % lim; } ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); } // END: random/base.hpp #line 6 "main.cpp" void solve() { INT(N); #ifdef LOCAL vc god(N); FOR(i, N) god[i] = RNG(1, N + 1); #endif auto ASK = [&](vc A) -> bool { if (A.empty()) return 1; print("?", len(A), A); #ifdef LOCAL return is_subseq(A, god); #endif STR(S); return (S == "Yes"); }; vc S; FOR(a, 1, N + 1) { int K = 0; while (len(S) + K < N) { vc T(K + 1, a); if (!ASK(T)) break; ++K; } while (K > 0) { // a^K int n = len(S); int m = binary_search( [&](int m) -> bool { vc T; FOR(i, m) T.eb(S[i]); FOR(K) T.eb(a); return ASK(T); }, 0, len(S) + 1); S.insert(S.begin() + m, a); --K; } } print("!", S); #ifdef LOCAL SHOW(god, S); assert(god == S); #endif } signed main() { solve(); } // END: main.cpp