#1195404 (C++23) No.3778 pow2!!pow2!!pow2!!

• 問題: No.3778 pow2!!pow2!!pow2!!
• ユーザー: Today03
• 提出日時: 2026-10-25 22:43:20
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 33,314 bytes
• コンパイル時間: 1,958 ms
• コンパイル使用メモリ: 279,892 KB
• 実行使用メモリ: 9,828 KB
• 最終ジャッジ日時: 2026-10-25 22:43:25
• 合計ジャッジ時間: 3,936 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge7_0

ファイルパターン	結果
other	AC * 7

ソースコード

//---------------->8----------------------------------------------------->8----------------
// Today03
// created : 2026-10-24 21:00:03
// copied  : 2026-10-25 22:43:16
// library : https://judge.yosupo.jp/submission/413060
// version : 2026-10-24 17:56:52
//---------------->8----------------------------------------------------->8----------------

// begin: kyopro_library/template.hpp
// begin: kyopro_library/base/include.hpp

#include <iostream>
#include <algorithm>
#include <type_traits>
#include <vector>
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <utility>
#include <chrono>
#include <cstring>
#include <cstdlib>
#include <cerrno>
#include <cassert>

using namespace std;
// end: kyopro_library/base/include.hpp

// begin: kyopro_library/base/type.hpp

using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = unsigned long long;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;

using ii = i64;
using ll = i64;
using ull = u64;
using lll = i128;
using ulll = u128;
using ld = f80;
using str = string;
using ii3 = array<ii, 3>;
using ii4 = array<ii, 4>;
using ii5 = array<ii, 5>;
constexpr ii operator""_ii(ull x) { return static_cast<ii>(x); }
constexpr lll operator""_lll(ull x) { return static_cast<lll>(x); }

template <typename T>
struct myvec : vector<T> {
    using vector<T>::vector;
    myvec() = default;
    myvec(const vector<T>& v) : vector<T>(v) {}
    myvec(vector<T>&& v) : vector<T>(std::move(v)) {}
#ifdef TDY
    decltype(auto) operator[](ii i) {
        if(i < 0 || i >= (ii)this->size()) {
            cout << "ERROR!" << endl;
            cout << "size is " << this->size() << ", but indexed " << i << endl;
        }
        return this->at(i);
    }
    decltype(auto) operator[](ii i) const {
        if(i < 0 || i >= (ii)this->size()) {
            cout << "ERROR!" << endl;
            cout << "size is " << this->size() << ", but indexed " << i << endl;
        }
        return this->at(i);
    }
#endif
};

template <typename T>
using V = myvec<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<VV<T>>;
template <typename T>
using VVVV = V<VVV<T>>;
template <typename T>
using VVVVV = V<VVVV<T>>;
template <typename T>
using VVVVVV = V<VVVVV<T>>;

using vi = V<ii>;
using vvi = VV<ii>;
using vvvi = VVV<ii>;
using vl = V<ll>;
using vvl = VV<ll>;
using vvvl = VVV<ll>;
using vlll = V<lll>;
using vvlll = VV<lll>;
using vstr = V<str>;

template <typename T>
using max_pq = priority_queue<T>;
template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using unset = unordered_set<T>;
template <typename T, typename T2>
using unmap = unordered_map<T, T2>;

template <typename T, typename U>
struct mypr : pair<T, U> {
    template <typename... Args>
        requires is_constructible_v<pair<T, U>, Args...>
    mypr(Args... args) : pair<T, U>(args...) {}
    mypr(const T& a, const U& b) : pair<T, U>(a, b) {}
    mypr() = default;
    using pair<T, U>::first;
    using pair<T, U>::second;
    mypr& operator+=(const mypr& r) {
        first += r.first;
        second += r.second;
        return *this;
    }
    mypr& operator-=(const mypr& r) {
        first -= r.first;
        second -= r.second;
        return *this;
    }
    mypr& operator*=(const mypr& r) {
        first *= r.first;
        second *= r.second;
        return *this;
    }
    template <typename S>
    mypr& operator+=(const S& r) {
        first += r;
        second += r;
        return *this;
    }
    template <typename S>
    mypr& operator-=(const S& r) {
        first -= r;
        second -= r;
        return *this;
    }
    template <typename S>
    mypr& operator*=(const S& r) {
        first *= r;
        second *= r;
        return *this;
    }
    mypr operator+(const mypr& r) const { return mypr(*this) += r; }
    mypr operator-(const mypr& r) const { return mypr(*this) -= r; }
    mypr operator*(const mypr& r) const { return mypr(*this) *= r; }
    template <typename S>
    mypr operator+(const S& r) const { return mypr(*this) += r; }
    template <typename S>
    mypr operator-(const S& r) const { return mypr(*this) -= r; }
    template <typename S>
    mypr operator*(const S& r) const { return mypr(*this) *= r; }
    mypr operator-() const { return mypr{-first, -second}; }
};
using pi = mypr<ii, ii>;
using vpi = V<pi>;
using vvpi = VV<pi>;
using pl = mypr<ll, ll>;
using vpl = V<pl>;
using vvpl = VV<pl>;

template <typename T, typename U, typename W>
struct mytr : tuple<T, U, W> {
    using tuple<T, U, W>::tuple;
    T& x = get<0>(*this);
    U& y = get<1>(*this);
    W& z = get<2>(*this);
    mytr() = default;
    mytr(const T& a, const U& b, const W& c) : tuple<T, U, W>(a, b, c) {}
    mytr(const mytr& other) : tuple<T, U, W>(other), x(get<0>(*this)), y(get<1>(*this)), z(get<2>(*this)) {}
    mytr(mytr&& other) noexcept : tuple<T, U, W>(move(other)), x(get<0>(*this)), y(get<1>(*this)), z(get<2>(*this)) {}
    mytr& operator=(const mytr& other) {
        tuple<T, U, W>::operator=(other);
        return *this;
    }
    mytr& operator=(mytr&& other) noexcept {
        tuple<T, U, W>::operator=(move(other));
        return *this;
    }
};
template <typename T, typename U, typename W>
struct std::tuple_size<mytr<T, U, W>> : integral_constant<size_t, 3> {};
template <size_t I, typename T, typename U, typename W>
struct std::tuple_element<I, mytr<T, U, W>> : tuple_element<I, tuple<T, U, W>> {};
using ti = mytr<ii, ii, ii>;
using vti = V<ti>;
using vvti = VV<ti>;
using tl = mytr<ll, ll, ll>;
using vtl = V<tl>;
using vvtl = VV<tl>;

constexpr const i32 INFI = 1e9 + 10;
constexpr const i64 INFL = 4e18;
constexpr const i128 INFLL = [] {
    i128 ret = 8;
    for(ii t = 0; t < 36; t++) ret *= 10;
    return ret;  // 8e36
}();

template <typename T>
constexpr T inf = 0;
template <>
constexpr i32 inf<i32> = INFI;
template <>
constexpr i64 inf<i64> = INFL;
template <>
constexpr i128 inf<i128> = INFLL;
template <>
constexpr u32 inf<u32> = INFI;
template <>
constexpr u64 inf<u64> = INFL;
template <>
constexpr u128 inf<u128> = INFLL;
template <>
constexpr f64 inf<f64> = numeric_limits<f64>::infinity();
template <>
constexpr f80 inf<f80> = numeric_limits<f80>::infinity();

istream& operator>>(istream& is, i128& x) {
    int c = is.peek();
    while(c == ' ' || c == '\n') is.get(), c = is.peek();
    bool neg = false;
    if(c == '-') neg = true, is.get();
    x = 0;
    while(isdigit(is.peek())) x = x * 10 + is.get() - '0';
    if(neg) x = -x;
    return is;
}

ostream& operator<<(ostream& os, i128 x) {
    if(x < 0) os << '-', x = -x;
    if(x == 0) return os << '0';
    string s;
    while(x > 0) s += char('0' + x % 10), x /= 10;
    reverse(s.begin(), s.end());
    return os << s;
}

#ifdef TDY
i128 abs(i128 x) {
    if(x < 0) return -x;
    return x;
}
i128 gcd(i128 a, i128 b) {
    while(b) a %= b, swap(a, b);
    return a;
}
#endif
// end: kyopro_library/base/type.hpp

// #include "kyopro_library/base/fastio.hpp"
// #include "kyopro_library/base/fastio_impl.hpp"
// begin: kyopro_library/base/macro.hpp

#define rep1(n) for(ii aaaaa = 0; aaaaa < (n); aaaaa++)
#define rep2(i, n) for(ii i = 0; i < (n); i++)
#define rep3(i, a, b) for(ii i = (a); i < (b); i++)
#define rep4(i, a, b, c) for(ii i = (a); i < (b); i += (c))
#define rep_overload(a, b, c, d, e, ...) e
#define rep(...) rep_overload(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define per1(n) for(ii aaaaa = (n) - 1; aaaaa >= 0; aaaaa--)
#define per2(i, n) for(ii i = (n) - 1; i >= 0; i--)
#define per3(i, a, b) for(ii i = (b) - 1; i >= (a); i--)
#define per4(i, a, b, c) for(ii i = (b) - 1; i >= (a); i -= (c))
#define per_overload(a, b, c, d, e, ...) e
#define per(...) per_overload(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)

#define each(x, a) for(auto& x : a)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define QYN(q, a, b) ((q) ? (a) : (b))

#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define mkt make_tuple
#define fi first
#define se second

// vの各要素にfを作用させる
#define dov(v, f)         \
    [&]() {               \
        auto&& _v = (v);  \
        for(auto& x : _v) \
            f(x);         \
    }()
// vの各要素xに対してf(x)からなる配列を返す
#define mkv(v, f)                                            \
    [&]() {                                                  \
        auto&& _v = (v);                                     \
        using Type = std::decay_t<decltype(f(*_v.begin()))>; \
        V<Type> ret;                                         \
        ret.reserve(_v.size());                              \
        for(const auto& x : _v)                              \
            ret.push_back(f(x));                             \
        return ret;                                          \
    }()

// 宣言&入力
#define II(...)     \
    ii __VA_ARGS__; \
    input(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    input(__VA_ARGS__)
#define LLL(...)     \
    lll __VA_ARGS__; \
    input(__VA_ARGS__)
#define IDX(...)        \
    ii __VA_ARGS__;     \
    input(__VA_ARGS__); \
    input_index(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    input(__VA_ARGS__);
#define CHR(...)      \
    char __VA_ARGS__; \
    input(__VA_ARGS__);
#define LD(...)     \
    ld __VA_ARGS__; \
    input(__VA_ARGS__);
#define VI(A, N) \
    vi A(N);     \
    input(A);
#define VVI(A, N, M) \
    vvi A(N, vi(M)); \
    input(A);
#define VL(A, N) \
    vl A(N);     \
    input(A);
#define VVL(A, N, M) \
    vvl A(N, vl(M)); \
    input(A);
#define VPI(A, N) \
    vpi A(N);     \
    input(A);
#define VTI(A, N) \
    vti A(N);     \
    input(A);
#define VI2(A, B, N) \
    vi A(N), B(N);   \
    rep(i, N) cin >> A[i] >> B[i];
#define VL2(A, B, N) \
    vl A(N), B(N);   \
    rep(i, N) cin >> A[i] >> B[i];
#define VI3(A, B, C, N)  \
    vi A(N), B(N), C(N); \
    rep(i, N) cin >> A[i] >> B[i] >> C[i];
#define VL3(A, B, C, N)  \
    vl A(N), B(N), C(N); \
    rep(i, N) cin >> A[i] >> B[i] >> C[i];
#define VI4(A, B, C, D, N)     \
    vi A(N), B(N), C(N), D(N); \
    rep(i, N) cin >> A[i] >> B[i] >> C[i] >> D[i];
#define VST(A, N) \
    vstr A(N);    \
    input(A);
#define IN2(A, B) rep(i, siz(A)) cin >> A[i] >> B[i];
#define IN3(A, B, C) rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i];
#define IN4(A, B, C, D) rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i] >> D[i];
#define IN5(A, B, C, D, E) \
    rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i] >> D[i] >> E[i];
// end: kyopro_library/base/macro.hpp

// begin: kyopro_library/base/io.hpp

/*
 * 入出力まわりの便利関数と、コンテナ・組の operator>> / operator<<。
 *  - 入力: input(a, b, ...) / input_index (1-indexed を 0-indexed に直す)
 *  - 出力: say (空白区切りで出して改行), line (改行しない), put (区切りなし), esay (ローカルのみ stderr へ)
 *  - 配列は空白区切り、2 次元配列は行ごとに改行、3 次元配列はブロックごとに空行で区切る
 * V<T> (myvec) は vector<T> の派生なので vector 版の operator で受けられるが、operator<< の
 * vector<vector<T>> 版は内側が myvec だとマッチしない (テンプレート引数の照合は厳密) ため、
 * V<V<T>> / V<V<V<T>>> 用の overload を別に置く。
 */

const char NL = '\n';
void flush() { cout.flush(); }

const string Yes = "Yes";
const string No = "No";
const string YES = "YES";
const string NO = "NO";
const string ALICE = "Alice";
const string BOB = "Bob";
const string FIRST = "First";
const string SECOND = "Second";
inline string YesNo(bool f) { return f ? Yes : No; }
inline string YESNO(bool f) { return f ? YES : NO; }
inline string AliBo(bool f) { return f ? ALICE : BOB; }
inline string FiSe(bool f) { return f ? FIRST : SECOND; }

template <typename T>
istream& operator>>(istream& is, vector<vector<T>>& v) {
    for(auto& x : v)
        for(auto& y : x) is >> y;
    return is;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for(auto& x : v) is >> x;
    return is;
}
// V<T> 用 (util.hpp の operator>>(const U&, V<T>) と曖昧にならないよう、両引数が完全一致する overload を置く)
template <typename T>
istream& operator>>(istream& is, V<T>& v) {
    for(auto& x : v) is >> x;
    return is;
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2, typename T3>
istream& operator>>(istream& is, tuple<T1, T2, T3>& t) {
    is >> get<0>(t) >> get<1>(t) >> get<2>(t);
    return is;
}
template <typename T1, typename T2, typename T3>
istream& operator>>(istream& is, mytr<T1, T2, T3>& t) {
    is >> get<0>(t) >> get<1>(t) >> get<2>(t);
    return is;
}

template <class... T>
void input(T&... a) { (cin >> ... >> a); }

template <class T>
void input_index(T& a) { a--; }
template <class T, class... Ts>
void input_index(T& a, Ts&... b) {
    a--;
    input_index(b...);
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const mypr<T1, T2>& p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
    return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const mytr<T1, T2, T3>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
    return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t) << ' ' << get<3>(t);
    return os;
}

// 配列の出力本体。vector 版と V 版の両方からこれを呼ぶ
template <typename A>
ostream& write_vec1(ostream& os, const A& a) {
    ii n = a.size();
    for(ii i = 0; i < n; i++) {
        os << a[i];
        if(i != n - 1) os << ' ';
    }
    return os;
}
template <typename A>
ostream& write_vec2(ostream& os, const A& a) {
    ii n = a.size();
    for(ii i = 0; i < n; i++) {
        write_vec1(os, a[i]);
        if(i != n - 1) os << NL;
    }
    return os;
}
template <typename A>
ostream& write_vec3(ostream& os, const A& a) {
    ii n = a.size();
    for(ii i = 0; i < n; i++) {
        write_vec2(os, a[i]);
        os << NL;
        if(i != n - 1) os << NL;
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<vector<T>>>& a) { return write_vec3(os, a); }
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& a) { return write_vec2(os, a); }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) { return write_vec1(os, a); }
template <typename T>
ostream& operator<<(ostream& os, const V<V<V<T>>>& a) { return write_vec3(os, a); }
template <typename T>
ostream& operator<<(ostream& os, const V<V<T>>& a) { return write_vec2(os, a); }
template <typename T>
ostream& operator<<(ostream& os, const V<T>& a) { return write_vec1(os, a); }

template <typename T>
ostream& operator<<(ostream& os, const set<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, queue<T> a) {
    while(!a.empty()) {
        os << a.front();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, priority_queue<T> a) {
    while(!a.empty()) {
        os << a.top();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, priority_queue<T, vector<T>, greater<T>> a) {
    while(!a.empty()) {
        os << a.top();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T, auto N>
ostream& operator<<(ostream& os, array<T, N> a) {
    for(ii i = 0; i < (ii)N; i++) {
        os << a[i];
        if(i != (ii)N - 1) os << ' ';
    }
    return os;
}

template <class T, class... Ts>
void put(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << b);
}

template <class T, class... Ts>
void line(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << (cout << ' ', b));
    cout << ' ';
}

void say() { cout << '\n'; }
template <class T, class... Ts>
void say(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << (cout << ' ', b));
    cout << NL;
}

void esay() {
#ifdef TDY
    flush();
    cerr << NL;
#endif
}
template <class T, class... Ts>
void esay(const T& a, const Ts&... b) {
#ifdef TDY
    flush();
    cerr << a;
    (void)(cerr << ... << (cerr << ' ', b));
    cerr << NL;
#endif
}

#define O(...)            \
    {                     \
        say(__VA_ARGS__); \
        return;           \
    }
// end: kyopro_library/base/io.hpp

// begin: kyopro_library/base/util.hpp

// https://trap.jp/post/1224/
template <class... T>
constexpr auto min(T... a) {
    return min(initializer_list<common_type_t<T...>>{a...});
}

template <class... T>
constexpr auto max(T... a) {
    return max(initializer_list<common_type_t<T...>>{a...});
}

template <typename A, typename B>
bool chmin(A& a, B b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename A, typename B>
bool chmax(A& a, B b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

// A/B以下の最大の整数
template <typename A, typename B>
constexpr common_type_t<A, B> myfloor(A a, B b) {
    assert(b != 0);
    if(b < 0) a = -a, b = -b;
    return a / b - (a % b < 0);
}

// A/B以上の最小の整数
template <typename A, typename B>
constexpr common_type_t<A, B> myceil(A a, B b) {
    assert(b != 0);
    if(b < 0) a = -a, b = -b;
    return a / b + (a % b > 0);
}

// A%B(in [0,B))
template <typename A, typename B>
constexpr common_type_t<A, B> mymod(A a, B b) {
    assert(b != 0);
    if(b < 0) b = -b;
    if(a > 0) return a % b;
    return (a % b + b) % b;
}

// LCM
template <typename A, typename B>
constexpr common_type_t<A, B> mylcm(A a, B b) {
    using T = common_type_t<A, B>;
    T g = gcd<T>(a, b);
    return T(a) / g * b;
}

template <typename T>
inline ii siz(const T& v) { return v.size(); }

template <typename T>
T minv(const vector<T>& v) {
    if(v.empty()) return inf<T>;
    return *min_element(all(v));
}
template <typename T>
T maxv(const vector<T>& v) {
    if(v.empty()) return -inf<T>;
    return *max_element(all(v));
}
template <typename T>
ii minidx(const vector<T>& v) { return min_element(all(v)) - v.begin(); }
template <typename T>
ii maxidx(const vector<T>& v) { return max_element(all(v)) - v.begin(); }
template <typename T>
T sumv(const vector<T>& v) { return reduce(v.begin(), v.end()); }
template <typename T>
ii lob(const vector<T>& v, const T& x) { return lower_bound(all(v), x) - v.begin(); }
template <typename T>
ii upb(const vector<T>& v, const T& x) { return upper_bound(all(v), x) - v.begin(); }
template <typename T>
ii findv(const vector<T>& v, const T& x) {
    for(ii i = 0; i < siz(v); i++)
        if(v[i] == x) return i;
    return siz(v);
}
template <typename T>
ii find_lastv(const vector<T>& v, const T& x) {
    for(ii i = siz(v) - 1; i >= 0; i--)
        if(v[i] == x) return i;
    return -1;
}

// ソート
template <typename T>
void doso(T& v) { sort(v.begin(), v.end()); }

template <typename T>
void doso(T& v, auto cmp) { sort(v.begin(), v.end(), cmp); }

template <typename T>
T mkso(const T& v) {
    auto w = v;
    doso(w);
    return w;
}

template <typename T>
T mkso(const T& v, auto cmp) {
    auto w = v;
    doso(w, cmp);
    return w;
}

// 逆順ソート
template <typename T>
void dosor(T& v) {
    sort(v.rbegin(), v.rend());
}

template <typename T>
T mksor(const T& v) {
    auto w = v;
    dosor(w);
    return w;
}

// ソート→重複削除
template <typename T>
void douniq(vector<T>& v) {
    sort(all(v));
    v.erase(unique(v.begin(), v.end()), v.end());
}

template <typename T>
V<T> mkuniq(const vector<T>& v) {
    auto w = v;
    douniq(w);
    return w;
}

// 座標圧縮
template <typename T>
V<T> mkcomp(vector<T> v) {
    auto w = v;
    douniq(w);
    for(T& x : v) x = lob(w, x);
    return v;
}

// aの中のvの個数を返す
ii countv(const auto& a, auto v) {
    return count(a.begin(), a.end(), v);
}

// aのidx番目にvを挿入する（..., a[idx-1], v, a[idx], ...）
void doinsert(auto& a, ii idx, auto v) {
    assert(idx <= siz(a));
    a.insert(a.begin() + idx, v);
}

auto mkinsert(const auto& a, ii idx, auto v) {
    auto b = a;
    doinsert(b, idx, v);
    return b;
}

// aのidx番目を削除する
void doerase(auto& a, ii idx) {
    assert(idx < siz(a));
    a.erase(a.begin() + idx);
}

auto mkerase(const auto& a, ii idx) {
    auto b = a;
    doerase(b, idx);
    return b;
}

// 先頭をoffset個分後ろに
void dorotateback(auto& a, ii offset) {
    offset %= siz(a);
    rotate(a.begin(), a.end() - offset, a.end());
}

// 末尾をoffset個分前の方に
void dorotatefront(auto& a, ii offset) {
    offset %= siz(a);
    rotate(a.begin(), a.begin() + offset, a.end());
}

auto mkpush(const auto& a, auto v) {
    auto b = a;
    b.push_back(v);
    return b;
}

// aの[l,r)を抜き出す
template <typename T>
V<T> mkslice(const vector<T>& a, ii l, ii r) {
    assert(l <= r && l >= 0 && r <= siz(a));
    V<T> b(a.begin() + l, a.begin() + r);
    return b;
}

// aとbを連結した配列を返す
template <typename T>
V<T> mkconcat(const vector<T>& a, const vector<T>& b) {
    auto ret = a;
    ret.reserve(siz(a) + siz(b));
    for(auto x : b) ret.push_back(x);
    return ret;
}

// aの後ろにbをくっつける
template <typename T>
void doconcat(vector<T>& a, const vector<T>& b) {
    for(auto x : b) a.push_back(x);
}

// a,bから{(a[0],b[0]), (a[1],b[1]), ...}を作る めっちゃ便利
template <typename A, typename B>
V<mypr<A, B>> zip(const vector<A>& a, const vector<B>& b) {
    ii n = siz(a);
    V<mypr<A, B>> ret(n);
    for(ii i = 0; i < n; i++) ret[i] = {a[i], b[i]};
    return ret;
}

template <typename A, typename B, typename C>
V<mytr<A, B, C>> zip(const vector<A>& a, const vector<B>& b, const vector<C>& c) {
    ii n = siz(a);
    V<mytr<A, B, C>> ret(n);
    for(ii i = 0; i < n; i++) ret[i] = {a[i], b[i], c[i]};
    return ret;
}

template <typename A, typename B>
mypr<V<A>, V<B>> unzip(const vector<mypr<A, B>>& p) {
    ii n = siz(p);
    V<A> reta(n);
    V<B> retb(n);
    for(ii i = 0; i < n; i++) {
        reta[i] = p[i].first;
        retb[i] = p[i].second;
    }
    return {reta, retb};
}

template <typename A, typename B, typename C>
mytr<V<A>, V<B>, V<C>> unzip(const vector<mytr<A, B, C>>& p) {
    ii n = siz(p);
    V<A> reta(n);
    V<B> retb(n);
    V<C> retc(n);
    for(ii i = 0; i < n; i++) {
        auto [a, b, c] = p[i];
        reta[i] = a;
        retb[i] = b;
        retc[i] = c;
    }
    return {reta, retb, retc};
}

template <typename T>
T pick(max_pq<T>& v) {
    T ret = v.top();
    v.pop();
    return ret;
}
template <typename T>
T pick(min_pq<T>& v) {
    T ret = v.top();
    v.pop();
    return ret;
}
template <typename T>
T pick(queue<T>& v) {
    T ret = v.front();
    v.pop();
    return ret;
}
template <typename T>
T pick(vector<T>& v) {
    T ret = v.back();
    v.pop_back();
    return ret;
}
template <typename T>
T pickf(deque<T>& v) {
    T ret = v.front();
    v.pop_front();
    return ret;
}
template <typename T>
T pickb(deque<T>& v) {
    T ret = v.back();
    v.pop_back();
    return ret;
}

template <typename T>
bool nxperm(T& v) { return next_permutation(v.begin(), v.end()); }

template <typename T>
V<T>& operator++(V<T>& a) {
    for(auto& x : a) ++x;
    return a;
}

template <typename T>
V<T> operator++(V<T>& a, int) {
    V<T> res = a;
    ++a;
    return res;
}

template <typename T>
V<T>& operator--(V<T>& a) {
    for(auto& x : a) --x;
    return a;
}

template <typename T>
V<T> operator--(V<T>& a, int) {
    V<T> res = a;
    --a;
    return res;
}

#define DEFINE_VECTOR_OP(OP)                             \
    template <typename T, typename U>                    \
    V<T>& operator OP##=(V<T>& a, const U & b) {         \
        for(auto& x : a) x OP## = b;                     \
        return a;                                        \
    }                                                    \
    template <typename T, typename U>                    \
    V<T>& operator OP##=(V<T>& a, const V<U>& b) {       \
        assert(a.size() == b.size());                    \
        for(ii i = 0; i < siz(a); i++) a[i] OP## = b[i]; \
        return a;                                        \
    }                                                    \
    template <typename T, typename U>                    \
    V<T> operator OP(V<T> a, const U & b) {              \
        a OP## = b;                                      \
        return a;                                        \
    }                                                    \
    template <typename T, typename U>                    \
    V<T> operator OP(const U & a, V<T> b) {              \
        for(auto& x : b) x = a OP x;                     \
        return b;                                        \
    }                                                    \
    template <typename T, typename U>                    \
    V<T> operator OP(V<T> a, const V<U>& b) {            \
        a OP## = b;                                      \
        return a;                                        \
    }

DEFINE_VECTOR_OP(+)
DEFINE_VECTOR_OP(-)
DEFINE_VECTOR_OP(*)
DEFINE_VECTOR_OP(/)
DEFINE_VECTOR_OP(%)
DEFINE_VECTOR_OP(&)
DEFINE_VECTOR_OP(|)
DEFINE_VECTOR_OP(^)

#undef DEFINE_VECTOR_OP

template <typename T>
V<T> mkvec(ii n, T init) {
    return V<T>(n, init);
}
template <typename... Ts>
auto mkvec(ii n, Ts... ts) {
    return V<decltype(mkvec(ts...))>(n, mkvec(ts...));
}

template <typename T = i64, typename U>
V<T> mksum(const vector<U>& v) {
    ii n = siz(v);
    V<T> ret(n + 1);
    for(ii i = 0; i < n; i++) ret[i + 1] = ret[i] + v[i];
    return ret;
}

template <typename T>
V<T> mkprefmax(const vector<T>& v) {
    ii n = siz(v);
    V<T> ret(n + 1, -inf<T>);
    for(ii i = 0; i < n; i++) ret[i + 1] = max(ret[i], v[i]);
    return ret;
}

template <typename T>
V<T> mkprefmin(const vector<T>& v) {
    ii n = siz(v);
    V<T> ret(n + 1, inf<T>);
    for(ii i = 0; i < n; i++) ret[i + 1] = min(ret[i], v[i]);
    return ret;
}

template <typename T>
V<T> mksuffmax(const vector<T>& v) {
    ii n = siz(v);
    V<T> ret(n + 1, -inf<T>);
    for(ii i = n - 1; i >= 0; i--) ret[i] = max(ret[i + 1], v[i]);
    return ret;
}

template <typename T>
V<T> mksuffmin(const vector<T>& v) {
    ii n = siz(v);
    V<T> ret(n + 1, inf<T>);
    for(ii i = n - 1; i >= 0; i--) ret[i] = min(ret[i + 1], v[i]);
    return ret;
}

vi mkiota(ii n) {
    vi ret(n);
    iota(ret.begin(), ret.end(), 0);
    return ret;
}

template <typename T>
T mkrev(T a) {
    reverse(a.begin(), a.end());
    return a;
}

template <typename T>
void dorev(T& a) {
    reverse(a.begin(), a.end());
}

vi mkinv(const vi& a, ii mx = -1) {
    ii n = siz(a);
    if(mx == -1) mx = maxv(a) + 1;
    vi ret(mx);
    for(ii i = 0; i < n; i++) ret[a[i]] = i;
    return ret;
}

vvi mkinvvec(const vi& a, ii mx = -1) {
    ii n = siz(a);
    if(mx == -1) mx = maxv(a) + 1;
    vvi ret(mx);
    for(ii i = 0; i < n; i++) ret[a[i]].push_back(i);
    return ret;
}

vi mkfreq(const vi& a, ii mx = -1) {
    ii n = siz(a);
    if(mx == -1) mx = maxv(a) + 1;
    vi ret(mx);
    for(ii i = 0; i < n; i++) ret[a[i]]++;
    return ret;
}

template <typename T>
vi mkarg(const vector<T>& a) {
    vi ret = mkiota(siz(a));
    sort(ret.begin(), ret.end(), [&](ii i, ii j) {
        return (a[i] == a[j] ? i < j : a[i] < a[j]);
    });
    return ret;
}

template <typename T>
constexpr ii digit_siz(T n) {
    ii ret = 0;
    while(n) {
        ret++;
        n /= 10;
    }
    return ret;
}

template <typename T>
constexpr vi digits(T n) {
    vi ret;
    while(n) {
        ret.push_back(n % 10);
        n /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

template <typename T = i64>
constexpr T intpow(T x, T r) {
    T ret = 1;
    while(r) {
        if(r & 1) ret *= x;
        x *= x;
        r >>= 1;
    }
    return ret;
}

constexpr i64 tenpow(ii r) {
    i64 ret = 1;
    while(r--) ret *= 10;
    return ret;
}

template <typename T>
constexpr T intsqrt(T x) {
    i64 sq = (T)sqrtl(ld(x));
    while(sq * sq > x) sq--;
    while((sq + 1) * (sq + 1) <= x) sq++;
    return sq;
}

template <typename T = i128>
constexpr T euc_dist(auto ax, auto ay, auto bx, auto by) {
    return T(ax - bx) * (ax - bx) + T(ay - by) * (ay - by);
}

template <typename T = i64>
constexpr T man_dist(auto ax, auto ay, auto bx, auto by) {
    return abs(T(ax) - bx) + abs(T(ay) - by);
}

constexpr ii lotoi(char c) {
    assert('a' <= c && c <= 'z');
    return c - 'a';
}

constexpr char itolo(ii i) {
    assert(0 <= i && i <= 25);
    return char('a' + i);
}

constexpr ii hitoi(char c) {
    assert('A' <= c && c <= 'Z');
    return c - 'A';
}

constexpr char itohi(ii i) {
    assert(0 <= i && i <= 25);
    return char('A' + i);
}

constexpr ii ctoi(char c) {
    assert('0' <= c && c <= '9');
    return c - '0';
}

constexpr char itoc(ii i) {
    assert(0 <= i && i <= 9);
    return char('0' + i);
}

vi stov(const str& s, char base = 'a') {
    vi ret(siz(s));
    rep(i, siz(s)) ret[i] = s[i] - base;
    return ret;
}

str vtos(const vi& a, char base = 'a') {
    str ret;
    rep(i, siz(a)) ret.push_back(char(base + a[i]));
    return ret;
}

constexpr ii popcount(i32 n) { return __builtin_popcount(n); }
constexpr ii popcount(i64 n) { return __builtin_popcountll(n); }
constexpr ii popcount(u32 n) { return __builtin_popcount(n); }
constexpr ii popcount(u64 n) { return __builtin_popcountll(n); }

constexpr ii parity(i32 n) { return __builtin_parity(n); }
constexpr ii parity(i64 n) { return __builtin_parityll(n); }

// 最上位ビットの位置
constexpr ii topbit(i32 n) { return n ? 31 - __builtin_clz(n) : -1; }
constexpr ii topbit(i64 n) { return n ? 63 - __builtin_clzll(n) : -1; }
constexpr ii topbit(u32 n) { return n ? 31 - __builtin_clz(n) : -1; }
constexpr ii topbit(u64 n) { return n ? 63 - __builtin_clzll(n) : -1; }

// 2進表現の長さ
constexpr ii bitsiz(i32 n) { return n ? 32 - __builtin_clz(n) : 1; }
constexpr ii bitsiz(i64 n) { return n ? 64 - __builtin_clzll(n) : 1; }

// 最下位ビットの位置
constexpr ii bottombit(i32 n) { return n ? __builtin_ctz(n) : -1; }
constexpr ii bottombit(i64 n) { return n ? __builtin_ctzll(n) : -1; }
constexpr ii bottombit(u32 n) { return n ? __builtin_ctz(n) : -1; }
constexpr ii bottombit(u64 n) { return n ? __builtin_ctzll(n) : -1; }

constexpr bool ispower2(i64 n) { return n && (n & -n) == n; }

constexpr i64 mkmask(ii n) { return (1LL << n) - 1; }

constexpr bool hasbit(i64 n, ii i) { return (n >> i & 1); }

vi mksubset(ii s) {
    vi ret;
    ii t = s;
    do {
        ret.push_back(t);
        --t &= s;
    } while(t != s);
    return ret;
}

// 2進数表記を返す
string tobinary(i64 n, ii len = 32, bool rev = false) {
    string ret;
    for(ii i = 0; i < len; i++) ret += (hasbit(n, rev ? len - 1 - i : i) ? '1' : '0');
    return ret;
}
// end: kyopro_library/base/util.hpp

#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif

void run();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(7);
#ifdef MULTI
    II(T);
    rep(T) {
#ifdef TDY
        // esay("============ Case: #", t + 1, " ============");
#endif
        run();
    }
#else
    run();
#endif
}
// end: kyopro_library/template.hpp

//------>8------------------------------------------->8------
/*
 */

void run() {
    STR(S);
    rep(siz(S)) put(S);
    put(NL);
}  // a.cpp
// 2026-10-25 22:43:16