Submission #64088442

---

Source Code Expand

// Problem: F - ABCBA
// Contest: AtCoder - UNIQUE VISION Programming Contest 2025 Spring (AtCoder Beginner Contest 398)
// URL: https://atcoder.jp/contests/abc398/tasks/abc398_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define multiple_cases(T) signed T; cin >> T; while (T--)
#define variable_name(x) #x
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
const int mod = 998244353;
namespace quick_io {
	template<typename T>
	void print(T a, string s = " ") {
		for (auto i : a) {
			cout << i << s;
		}
	}
	template<typename T>
	ostream &operator<<(ostream &A, vector<T> b);
	template<typename T1, typename T2>
	ostream &operator<<(ostream &A, pair<T1, T2> b);
	template<typename T>
	ostream &operator<<(ostream &A, set<T> b);
	template<typename T>
	ostream &operator<<(ostream &A, multiset<T> b);
	template<typename T, typename T2>
	ostream &operator<<(ostream &A, map<T, T2> b);
	template<typename T, typename T2>
	ostream &operator<<(ostream &A, multimap<T, T2> b);
	template<typename T>
	ostream &operator<<(ostream &A, unordered_set<T> b);
	template<typename T>
	ostream &operator<<(ostream &A, unordered_multiset<T> b);
	template<typename T, typename T2>
	ostream &operator<<(ostream &A, unordered_map<T, T2> b);
	template<typename T, typename T2>
	ostream &operator<<(ostream &A, unordered_multimap<T, T2> b);
	template<typename T>
	ostream &operator<<(ostream &A, vector<T> b) {
		A << "[";
		for (size_t i = 0; i + 1 < b.size(); i++) {
			A << b[i] << ",";
		}
		if (b.size()) {
			A << b[b.size() - 1];
		}
		A << "]";
		return A;
	}
	template<typename T1, typename T2>
	ostream &operator<<(ostream &A, pair<T1, T2> b) {
		return A << '(' << b.first << ',' << b.second << ')';
	}
	template<typename T>
	ostream &operator<<(ostream &A, set<T> b) {
		typename set<T>::iterator i = b.begin(), e = b.end();
		e--;
		A << "{";
		while (i != e) {
			A << *i << ",";
			i++;
		}
		A << *e << "}";
		return A;
	}
	template<typename T>
	ostream &operator<<(ostream &A, multiset<T> b) {
		typename multiset<T>::iterator i = b.begin(), e = b.end();
		e--;
		A << "{";
		while (i != e) {
			A << *i << ",";
			i++;
		}
		A << *e << "}";
		return A;
	}
	template<typename T, typename T2>
	ostream &operator<<(ostream &A, map<T, T2> b) {
		typename map<T, T2>::iterator i = b.begin(), e = b.end();
		e--;
		A << "{";
		while (i != e) {
			A << *i << ",";
			i++;
		}
		A << *e << "}";
		return A;
	}
	template<typename T, typename T2>
	ostream &operator<<(ostream &A, multimap<T, T2> b) {
		typename map<T, T2>::iterator i = b.begin(), e = b.end();
		e--;
		A << "{";
		while (i != e) {
			A << *i << ",";
			i++;
		}
		A << *e << "}";
		return A;
	}
	template<typename T>
	ostream &operator<<(ostream &A, unordered_set<T> b) {
		typename unordered_set<T>::iterator i = b.begin(), e = b.end();
		A << "{";
		while (i != e) {
			A << *i;
			i++;
			if (i != e) {
				cout << ",";
			}
		}
		A << "}";
		return A;
	}
	template<typename T>
	ostream &operator<<(ostream &A, unordered_multiset<T> b) {
		typename unordered_multiset<T>::iterator i = b.begin(), e = b.end();
		A << "{";
		while (i != e) {
			A << *i;
			i++;
			if (i != e) {
				cout << ",";
			}
		}
		A << "}";
		return A;
	}
	template<typename T, typename T2>
	ostream &operator<<(ostream &A, unordered_multimap<T, T2> b) {
		typename unordered_multimap<T, T2>::iterator i = b.begin(), e = b.end();
		A << "{";
		while (i != e) {
			A << *i;
			i++;
			if (i != e) {
				cout << ",";
			}
		}
		A << "}";
		return A;
	}
	template<typename T, typename T2>
	ostream &operator<<(ostream &A, unordered_map<T, T2> b) {
		typename unordered_map<T, T2>::iterator i = b.begin(), e = b.end();
		A << "{";
		while (i != e) {
			A << *i;
			i++;
			if (i != e) {
				cout << ",";
			}
		}
		A << "}";
		return A;
	}
	template<typename T>
	void print_array(T *b, T *e, string s = " ") {
		e--;
		while (b != e) {
			cout << *b << s;
			b++;
		}
		cout << *b;
	}
	template<typename T>
	void auto_print(T &b, size_t n, string s = " ") {
		for (size_t i = 1; i < n; i++) {
			cout << b[i] << s;
		}
		cout << b[n];
	}
	template<typename T>
	void print_n(T b, size_t n, string s = " ") {
		cout << *b;
		for (size_t i = 1; i < n; i++) {
			b++;
			cout << s << *b;
		}
	}
	template<typename T>
	void read_array(T *b, T *e) {
		while (b != e) {
			cin >> *b;
			b++;
		}
	}
	template<typename T>
	void auto_read(T &b, size_t n) {
		for (size_t i = 1; i <= n; i++) {
			cin >> b[i];
		}
	}
	template<typename T>
	void read_n(T b, size_t n) { // untested
		cin >> *b;
		for (size_t i = 1; i < n; i++) {
			b++;
			cin >> *b;
		}
	}
}
using quick_io::operator<<;
namespace MATH {
	template<typename Ta, typename Tb, typename Tm>
	Ta quickpower(Ta a, Tb b, Tm MOD) { // MOD \in P
		if (b < 0) {
			b = b % (MOD - 1) + MOD - 1;
		}
		a %= MOD;
		Ta c = 1;
		while (b) {
			if (b & 1) {
				c *= a;
				c %= MOD;
			}
			a *= a;
			a %= MOD;
			b >>= 1;
		}
		return c;
	}
	template<typename T>
	T gcd(T a, T b) {
		if (b == T(0))
			return a;
		return gcd(b, a % b);
	}
	template<typename T>
	T lcm(T a, T b) {
		return a * b / gcd(a, b);
	}
	template<typename T, typename T1, typename T2>
	T exgcd(T a, T b, T1 &x, T2 &y) { // untested
		if (b == 0) {
			x = 1;
			y = 0;
			return a;
		}
		T ans = exgcd(b, a % b, x, y);
		T1 X = y;
		T2 Y = (T2)x - ((T2)a / (T2)b) * y;
		x = X;
		y = Y;
		return ans;
	}
	template<typename T>
	T log2_(T k) {
		T l = 0, r = 62;
		while (l < r) {
			if ((1ll << ((l + r + 1) >> 1)) > k) {
				r = ((l + r + 1) >> 1) - 1;
			} else {
				l = ((l + r + 1) >> 1);
			}
		}
		return l;
	}
	template<typename T, typename T2>
	void build_power(T *power_array, T2 power_base, size_t len) {
		power_array[0] = 1;
		for (size_t i = 1; i <= len; i++) {
			power_array[i] = power_array[i - 1] * (T)power_base;
		}
	}
	template<typename T1, typename T2>
	void build_factorial(int n, T1 *f, T2 *inv) {
		f[0] = 1;
		for (int i = 1; i <= n; i++) {
			f[i] = f[i - 1] * (T1)i;
		}
		if (inv == nullptr) {
			return;
		}
		inv[n] = T2(1) / T2(f[n]);
		for (int i = n - 1; i >= 0; i--) {
			inv[i] = inv[i + 1] * (T2)(i + 1);
		}
	}
	template<typename T1, typename T2>
	T1 C(size_t n, size_t m, T1 *f, T2 *i) {
		return f[n] * (T1)i[m] * (T1)i[n - m];
	}
	// #define C(n, m, f, i) f[n] * i[m] * i[n - m] // define mod C
	template<typename T_fac, typename T_inv>
	T_fac Lucas_C(size_t n, size_t m, size_t p, T_fac *fac, T_inv *inv) {
		if (n < p && m < p) {
			return ((m > n) ? T_fac(0) : fac[n] * inv[m] % p * inv[n - m] % p);
		}
		return ((m % p > n % p) ? T_fac(0) : fac[n % p] * inv[m % p] % p * inv[n % p - m % p] % p * Lucas_C(n / p, m / p, p, fac, inv) % p);
	}
	template<typename T_fac, typename T_inv>
	T_fac Lucas(size_t n, size_t m, size_t p, T_fac *fac, T_inv *inv) // p \in Primes
	{
		T_fac *new_fac = fac;
		T_inv *new_inv = inv;
		if (new_fac == nullptr) new_fac = new T_fac[p];
		if (new_inv == nullptr) new_inv = new T_inv[p];
		new_fac[0] = 1;
		for (size_t i = 1; i < p; i++) {
			new_fac[i] = new_fac[i - 1] * T_fac(i) % T_fac(p);
		}
		new_inv[p - 1] = quickpower(new_fac[p - 1], p - 2, p);
		for (size_t i = p - 2; i <= p; i--) {
			new_inv[i] = new_inv[i + 1] * T_inv(i + 1) % T_inv(p);
		}
		T_fac ans = Lucas_C(n, m, p, new_fac, new_inv);
		if (new_fac != fac) delete[] new_fac;
		if (new_inv != inv) delete[] new_inv;
		return ans;
	}
	template<typename T_p, typename T_flag, typename T_minp>
	void build_prime(size_t n, T_p *p, T_flag *flag, T_minp *minp) {
		T_p *new_p = nullptr;
		T_flag *new_flag = nullptr;
		if (p == nullptr) {
			new_p = new T_p[n + 1];
		} else {
			new_p = p;
		}
		if (flag == nullptr) {
			new_flag = new T_flag[n + 1];
		} else {
			new_flag = flag;
		}
		new_p[0] = 0;
		fill_n(new_flag, n + 1, T_flag(true));
		minp[1] = 1;
		new_flag[1] = false;
		new_flag[1] = false;
		for (size_t i = 2; i <= n; i++) {
			if (new_flag[i]) {
				new_p[++new_p[0]] = i;
				minp[i] = i;
			}
			for (size_t j = 1; i * new_p[j] <= n; j++) {
				new_flag[i * new_p[j]] = false;
				minp[i * new_p[j]] = new_p[j];
				if (i % new_p[j] == size_t(0)) {
					break;
				}
			}
		}
		if (p != new_p) {
			delete[] new_p;
		}
		if (flag != new_flag) {
			delete[] new_flag;
		}
	}
	template<typename T_minp, typename T_mu>
	void build_mu(size_t n, T_minp *minp, T_mu *mu) {
		mu[1] = 1;
		for (size_t i = 2; i <= n; i++) {
			if (i / minp[i] % minp[i] == 0) {
				mu[i] = 0;
			} else {
				mu[i] = - mu[i / minp[i]];
			}
		}
	}
	template<typename T, typename T_mu, typename T_parameter>
	void mobius_inversion_multiple(size_t n, T (*g)(T_parameter), T *f, T_mu *mu) {
		for (size_t i = 1; i <= n; i++) {
			for (size_t j = 1; j * i <= n; j++) {
				f[i] += g(i * j) * T(mu[j]);
			}
		}
	}
	template<typename T, typename T_mu>
	void mobius_inversion_multiple(size_t n, T *g, T *f, T_mu *mu) {
		for (size_t i = 1; i <= n; i++) {
			for (size_t j = 1; j * i <= n; j++) {
				f[i] += g[i * j] * T(mu[j]);
			}
		}
	}
	template<typename T, typename T_mu, typename T_parameter>
	void mobius_inversion_divisor(size_t n, T (*g)(T_parameter), T *f, T_mu *mu) { // untested
		for (size_t i = 1; i <= n; i++) {
			for (size_t j = 1; j * i <= n; j++) {
				f[i * j] += g(i) * T(mu[j]);
			}
		}
	}
	template<typename T, typename T_mu>
	void mobius_inversion_divisor(size_t n, T *g, T *f, T_mu *mu) { // untested
		for (size_t i = 1; i <= n; i++) {
			for (size_t j = 1; j * i <= n; j++) {
				f[i * j] += g[i] * T(mu[j]);
			}
		}
	}
}
namespace Matrix {
	template<typename T>
	struct matrix {
		size_t n, m;
		vector<vector<T> > a;
		matrix() : n(0), m(0), a() {}
		matrix(size_t N, size_t M) {
			n = N;
			m = M;
			a = vector<vector<T> >(n, vector<T>(m, 0));
		}
		matrix(size_t N, size_t M, bool X) {
			n = N;
			m = M;
			a = vector<vector<T> >(n, vector<T>(m, 0));
			if (X) {
				for (size_t i = 0; i < n; i++) {
					a[i][i] = 1;
				}
			}
		}
		matrix(vector<vector<T> > A) {
			a = A;
			n = a.size();
			m = 0;
			for (size_t i = 0; i < n; i++) {
				m = max(m, (T)a[i].size());
			}
			for (size_t i = 0; i < n; i++) {
				a[i].insert(a[i].end(), m - a[i].size(), 0);
			}
		}
		void resize(size_t N, size_t M) { // untested
			if (n > N) {
				a.erase(a.begin() + N, a.end());
				n = N;
			} else if (n < N) {
				a.insert(a.end(), N - n, vector<T>(M, 0));
			}
			if (m > M) {
				for (size_t i = 0; i < n; i++) {
					a[i].insert(a.end(), M - m, 0);
				}
			} else if (m < M) {
				for (size_t i = 0; i < n; i++) {
					a[i].erase(a[i].begin() + M, a[i].end());
				}
			}
			n = N;
			m = M;
		}
		void get_e(size_t newn) {
			matrix(newn, newn, 1);
		}
		void memset(T x, size_t newn, size_t newm) {
			n = newn;
			m = newm;
			a = vector<vector<T> >(n, vector<T>(m, x));
		}
		void print() {
			for (size_t i = 0; i < n; i++) {
				for (size_t j = 0; j < m; j++) {
					cout << a[i][j] << " ";
				}
				cout << endl;
			}
		}
		matrix operator*(matrix b) {
			matrix<T> c(n, b.m, 0);
			for (size_t i = 0; i < n; i++) {
				for (size_t j = 0; j < b.m; j++) {
					for (size_t k = 0; k < m; k++) {
						c.a[i][j] += a[i][k] * b.a[k][j];
					}
				}
			}
			return c;
		}
		matrix operator*(T b) {
			matrix<T> c;
			c.memset(0, n, m);
			for (size_t i = 0; i < n; i++) {
				for (size_t j = 0; j < m; j++) {
					c.a[i][j] = a[i][j] * b;
				}
			}
			return c;
		}
		template<typename T2>
		matrix &operator*=(T2 b) { return *this = *this * b; }
		matrix operator^(long long b) {
			matrix c(n, n, 1), d = *this;
			while (b) {
				if (b & 1) {
					c *= d;
				}
				d *= d;
				b >>= 1;
			}
			return c;
		}
		vector<T> &operator[](size_t b) {
			return a[b];
		}
		T &operator[](pair<size_t, size_t> b) {
			return a[b.first][b.second];
		}
		template<typename T2>
		matrix &operator^=(T2 b) { return *this = *this ^ b; }
	};
	template<typename T, typename T2>
	T getsum(matrix<T> a, vector<T2> pos) {
		T ans = 0;
		for (T2 i : pos) {
			ans = (ans + a[i]) % mod;
		}
		return ans;
	}
	template<typename T>
	matrix<T> quickpower(matrix<T> a, long long b) {
		return a ^ b;
	}
	template<typename T>
	void print(matrix<T> a) {
		a.print();
	}
}
namespace graph_algorithm {
	#define graph_array(a, n, type) vector<type> a(n + 1)
	#define graph_array_val(n, type) vector<type>(n + 1)
	#define graph_array_t(type) vector<type>
	#define graph_vis(type) set<T>
	#define graph_index signed
	graph_index get_first_ele(short &x) { return x; }
	graph_index get_first_ele(unsigned short &x) { return x; }
	graph_index get_first_ele(signed &x) { return x; }
	graph_index get_first_ele(unsigned &x) { return x; }
	graph_index get_first_ele(long long &x) { return x; }
	graph_index get_first_ele(unsigned long long &x) { return x; }
	graph_index get_first_ele(__int128 &x) { return x; }
	template<typename T, typename T2>
	graph_index get_first_ele(pair<T, T2> &x) {
		return get_first_ele(x.first);
	}
	// directivity "d"/"u", weightiness "w"/"u"
	template<typename T>
	void read_graph_d_u(vector<T> *e, graph_index m) {
		T u, v;
		while (m--) {
			cin >> u >> v;
			e[u].push_back(v);
		}
	}
	template<typename T, typename T2>
	void read_graph_d_w(vector<pair<T, T2> > *e, graph_index m) {
		T u, v;
		T2 w;
		while (m--) {
			cin >> u >> v >> w;
			e[u].push_back({v, w});
		}
	}
	template<typename T>
	void read_graph_u_u(vector<T> *e, graph_index m) {
		T u, v;
		while (m--) {
			cin >> u >> v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
	}
	template<typename T, typename T2>
	void read_graph_u_w(vector<pair<T, T2> > *e, graph_index m) {
		T u, v;
		T2 w;
		while (m--) {
			cin >> u >> v >> w;
			e[u].push_back({v, w});
			e[v].push_back({u, w});
		}
	}
	template<typename T, size_t Col>
	void doubling_anc(T (*anc)[Col], graph_index n, signed m) { // untested
		for (graph_index i = 1; i <= n; i++) {
			for (signed j = 1; j <= m; j++) {
				anc[i][j] = anc[anc[i][j - 1]][j - 1];
			}
		}
	}
	template<typename T, size_t Row, size_t Col, typename T_dep>
	graph_index LCA(T (&anc)[Row][Col], T_dep *dep, graph_index x, graph_index y, size_t m = 30) { // untested
		m = min(m, Col - 1);
		if (dep[x] < dep[y]) {
			swap(x,y);
		}
		for (signed k = m; k >= 0; k--) {
			if (dep[anc[x][k]] >= dep[y]) {
				x = anc[x][k];
			}
		}
		if (x == y) return x;
		for (signed k = m; k >= 0; k--) {
			if (anc[x][k] != anc[y][k]) {
				x = anc[x][k];
				y = anc[y][k];
			}
		}
		return anc[x][0];
	}
	#undef graph_array
	#undef graph_array_val
	#undef graph_array_t
	#undef graph_vis
	#undef graph_index
}
namespace string_algorithm {
	#define string_index
	namespace hash {
		#define hash_int unsigned long long
		#define hash_transformation(x) ((x) - 'a' + 1)
		void build_hash(const string s, hash_int *hash_array, const hash_int hash_P) {
			if (s == "") {
				return;
			}
			hash_array[0] = hash_transformation(s[0]);
			for (size_t i = 1; i < s.size(); i++) {
				hash_array[i] = hash_array[i - 1] * hash_P + hash_transformation(s[i]);
			}
		}
		hash_int get_hash(size_t bgn, size_t ed, hash_int *hash_array, hash_int *p) {
			// cout << "(" << bgn << " " << ed << ")=";
			// if (bgn > ed) {
				// // cout << "(" << hash_array[ed] << " -" << hash_array[bgn + 1] << "*" << p[bgn - ed + 1] << ")";
				// return hash_array[ed] - hash_array[bgn + 1] * p[bgn - ed + 1];
			// }
			// cout << "(" << hash_array[ed] << "-" << hash_array[bgn - 1] << "*" << p[ed - bgn + 1] << ")";
			return hash_array[ed] - hash_array[bgn - 1] * p[ed - bgn + 1];
		}
		hash_int get_hash_r(size_t bgn, size_t ed, hash_int *hash_array, hash_int *p) {
			// cout << "R(" << bgn << " " << ed << ")=";
			// if (bgn > ed) {
				// cout << "(" << hash_array[ed] << " -" << hash_array[bgn + 1] << "*" << p[bgn - ed + 1] << ")";
				return hash_array[ed] - hash_array[bgn + 1] * p[bgn - ed + 1];
			// }
			// return hash_array[ed] - hash_array[bgn - 1] * p[ed - bgn + 1];
		}
		// #define get_hash(a, b, c, d) c[b] - c[(a) - 1] * d[(b) - (a) + 1] // define mod get_hash
		#undef hash_transformation
		#undef hash_int
	}
	#undef string_index
}
namespace data_structure {
	#define ds_index size_t
	#define linear_function_type long long
	#define lowbit(x) ((x)&-(x))
	#define ds_map(a, b, len) unordered_map<a, b >
	#define ds_vector(a) vector<a >
	namespace BIT {
		template<typename T>
		struct BIT {
			vector<T> t;
			BIT() {
				t = vector<T>(0, 0);
			}
			BIT(const ds_index n) {
				t = vector<T>(n, 0);
			}
			BIT(const ds_index n, T *a) {
				t = vector<T>(a, a + n);
				for (ds_index i = 1; i < n; i++) {
					if (i + lowbit(i) < n) {
						t[i + lowbit(i)] += t[i];
					}
				}
			}
			BIT(T *b, T *e) {
				t = vector<T>(b, e);
				ds_index n = t.size();
				for (ds_index i = 1; i < n; i++) {
					if (i + lowbit(i) < n) {
						t[i + lowbit(i)] += t[i];
					}
				}
			}
			BIT(const ds_index n, const T a) {
				t = vector<T>(n, a);
				for (ds_index i = 1; i < n; i++) {
					if (i + lowbit(i) < n) {
						t[i + lowbit(i)] += t[i];
					}
				}
			}
			void clear() {
				t = vector<T>(0, 0);
			}
			ds_index size() {
				return t.size();
			}
			void update(ds_index x, const T k) {
				if (x == 0) {
					t[0] += k;
				}
				while (x != 0 && x < t.size()) {
					t[x] += k;
					x += lowbit(x);
				}
			}
			T query(ds_index x) {
				T ans = t[0];
				while (x) {
					ans += t[x];
					x ^= lowbit(x);
				}
				return ans;
			}
			T query(const ds_index l, const ds_index r) {
				return query(r) - (l ? query(l - 1) : T(0));
			}
			T operator[](const ds_index b) {
				return query(b, b);
			}
			void resize(const ds_index n) {
				ds_index m = t.size();
				if (n <= t.size()) {
					t.erase(t.end() - n, t.end());
					return;
				}
				t.insert(t.end(), n - m, 0);
				for (ds_index i = 0; i < n; i++) {
					if (i + lowbit(i) >= m && i + lowbit(i) < n) {
						t[i + lowbit(i)] += t[i];
					}
				}
			}
		};
	}
	namespace ST {
		template<typename T, size_t Row, size_t Col>
		T query(const T (&st)[Row][Col], ds_index l, ds_index r, bool (*cmp)(T, T)) {
			if (l > r) swap(l, r);
			ds_index k = MATH::log2_(r - l + 1);
			if (cmp(st[l][k], st[r - (1 << k) + 1][k])) {
				return st[l][k];
			} else {
				return st[r - (1 << k) + 1][k];
			}
		}
		template<typename T, size_t Row, size_t Col>
		void build_ST(T (&st)[Row][Col], const ds_index n, bool (*cmp)(T, T)) {
			for (ds_index i = 1; ((ds_index)1 << i) <= n; i++) {
				for (ds_index j = 1; j + (1 << i) - 1 <= n; j++) {
					if (cmp(st[j][i - 1], st[j + (1 << (i - 1))][i - 1])) {
						st[j][i] = st[j][i - 1];
					} else {
						st[j][i] = st[j + (1 << (i - 1))][i - 1];
					}
				}
			}
		}
	}
	namespace DSU { // untested, can't use
		template<typename T_fa, typename T_sz, typename T_d>
		void build_DSU(const ds_index n, T_fa *fa, T_sz *sz, T_d *d) {
			for (ds_index i = 0; i <= n; i++) {
				fa[i] = i;
				if (sz != nullptr) {
					sz[i] = 1;
				}
				if (d != nullptr) {
					d[i] = 1;
				}
			}
		}
		template<typename T>
		ds_index getfa(const ds_index id, T *fa) {
			return ((fa[id] == id) ? id : (fa[id] = getfa(fa[id], fa)));
		}
		template<typename T, typename T_sz>
		void merge(ds_index u, ds_index v, T *fa, T_sz *sz) {
			u = getfa(u, fa);
			v = getfa(v, fa);
			if (u != v) {
				if (sz[u] <= sz[v]) {
					sz[v] += sz[u];
					fa[u] = fa[v];
				} else {
					sz[u] += sz[v];
					fa[v] = fa[u];
				}
			}
		}
		template<typename T>
		void merge(ds_index u, ds_index v, T *fa) {
			fa[getfa(u, fa)] = fa[getfa(v, fa)];
		}
	}
	#undef ds_index
	#undef linear_function_type
	#undef lowbit
	#undef ds_map
}
int quickpower(int a, int b) {
	if (b < 0) b = b % (mod - 1) + mod - 1;
	int c = 1;
	while (b) {
		if (b & 1) {
			c *= a;
			c %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return c;
}
template<typename T>
T auto_quickpower(T a, int b) {
	T c = 1;
	while (b) {
		if (b & 1) {
			c *= a;
		}
		a *= a;
		b >>= 1;
	}
	return c;
}
#define int unsigned long long
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>(y))?(x):(y))
#define lowbit(x) ((x)&-(x))
#define abs(x) (((x)<(0))?(-(x)):(x))
#define swap(a,b) a^=b^=a^=b
#define INF 1e18
#define P 10
using namespace string_algorithm::hash;
#define MAXN 1000005
int n, p[MAXN], hs1[MAXN], hs2[MAXN], ans;
string s;
signed main() {
	cin >> s;
	n = s.size();
	s = " " + s;
	p[0] = 1;
	for (int i = 1; i < MAXN; i++)
	{
		p[i] = p[i - 1] * P;
	}
	for (int i = 1; i <= n; i++)
	{
		hs1[i] = hs1[i - 1] * P + s[i] - 'A' + 1;
	}
	for (int i = n; i >= 1; i--)
	{
		hs2[i] = hs2[i + 1] * P + s[i] - 'A' + 1;
	}
	// for (int i = 1; i <= n; i++)
	// {
		// cout << hs1[i] << " ";
	// }
	// cout << endl;
	// for (int i = 1; i <= n; i++)
	// {
		// cout << hs2[i] << " ";
	// }
	// cout << endl;
	for (int i = 1; i <= n; i++)
	{
		if (i > n / 2)
		{
			// cout << i << " " << get_hash_r(i, 2 * i - n, hs2, p) << " " << get_hash(i, n, hs1, p) << endl;
			if (get_hash_r(i, 2 * i - n, hs2, p) == get_hash(i, n, hs1, p))
			{
				ans = i * 2 - 1;
				break;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (i > (n + 1) / 2)
		{
			if (get_hash_r(i - 1, 2 * i - n - 1, hs2, p) == get_hash(i, n, hs1, p))
			{
				ans = min(ans, i * 2 - 2);
				break;
			}
		}
	}
	// cout << ans << endl;
	// return 0;
	cout << s.substr(1);
	for (signed i = ans - n; i >= 0; i--)
	{
		cout << s[i];
	}
	return 0;
	for (int i = 1; i <= ans; i++)
	{
		cout << s[i];
	}
	for (int i = ans - 1; i >= 1; i--)
	{
		cout << s[i];
	}
	return 0;
}

Submission Info

Judge Result