結果
| 問題 | No.2737 Compound Word |
| ユーザー |
 ZOI-dayo
|
| 提出日時 | 2024-04-20 18:43:43 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 51,612 bytes |
| コンパイル時間 | 6,990 ms |
| コンパイル使用メモリ | 446,140 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-12 15:24:43 |
| 合計ジャッジ時間 | 7,913 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 |
ソースコード
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/alias.hpp"#include <boost/multiprecision/cpp_int.hpp>#include <bits/stdc++.h>using namespace std;// using namespace std::views;// using namespace boost::multiprecision;// --- 型エイリアス ---using ll = long long;using ull = unsigned long long;template <typename T> using vec = vector<T>;template <typename T> using vvec = vector<vector<T>>;template <typename T> using p_queue = priority_queue<T>;template <typename T> using rp_queue = priority_queue<T, vec<T>, greater<T>>;using bint = boost::multiprecision::cpp_int;// --- 黒魔術 ---#define int ll// --- 制御マクロ ---#define rep(i, n) for (ll i = 0; i < n; ++i)#define all(v) begin(v), end(v)// #define BIT(n) (1LL << (n))#define MAX(type) numeric_limits<type>::max()#define MIN(type) numeric_limits<type>::min()#define yes cout << "Yes" << endl#define no cout << "No" << endl#define pb push_back#define mp make_pair#define fir first#define sec second// --- 定数 ---constexpr ll INF = 1LL << 60;inline signed bit_width(ll x) { return bit_width((ull)x); }inline ull bit_ceil(ll x) { return bit_ceil((ull)x); }#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/concepts.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/concepts.hpp"template <class T>concept addable = requires(T a, T b) {{ a + b } -> convertible_to<T>;};#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/debug.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/debug.hpp"// --- デバッグ ---#ifndef ONLINE_JUDGE// #define printd(x) cerr << #x << ": " << x << endl;const string _TERM_ESC = "\033";const string _TERM_BOLD = _TERM_ESC + "[1m";const string _TERM_DECO_RESET = _TERM_ESC + "[0m";const string _TERM_FORE_RED = _TERM_ESC + "[31m";const string _TERM_FORE_RESET = _TERM_ESC + "[39m";const string _TERM_BACK_RED = _TERM_ESC + "[41m";const string _TERM_BACK_RESET = _TERM_ESC + "[49m";#define line_debug() cerr << "line: " << __LINE__ << endl;#define coutd(x) cerr << "[debug] " << x;#define printd(x) \cerr << _TERM_BOLD << _TERM_BACK_RED << "[debug] " << (#x) << " = " << (x) \<< _TERM_BACK_RESET << _TERM_DECO_RESET << endl;#else#define line_debug() ;#define coutd(x) ;#define printd(x) ;#endif#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/int128_t.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/int128_t.hpp"using int128_t = __int128_t;using uint128_t = __uint128_t;using lll = int128_t;using ulll = uint128_t;// https://kenkoooo.hatenablog.com/entry/2016/11/30/163533ostream &operator<<(ostream &dest, lll value) {ostream::sentry s(dest);if (s) {lll tmp = value < 0 ? -value : value;char buffer[128];char *d = end(buffer);do {--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(ios_base::badbit);}}return dest;}lll string_to_lll(string &s) {lll ret = 0;for (int i = 0; i < s.length(); i++)if ('0' <= s[i] && s[i] <= '9')ret = 10 * ret + s[i] - '0';return ret;}istream &operator>>(istream &src, lll &value) {string s;src >> s;value = string_to_lll(s);return src;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/print.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/print.hpp"// ---------------// ----- TOC -----template <typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p);template <typename T1, typename T2>istream &operator>>(istream &is, pair<T1, T2> &p);template <typename T> ostream &operator<<(ostream &os, const vector<T> &v);template <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &v);template <typename T>ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v);template <typename T> istream &operator>>(istream &is, vector<T> &v);template <typename T, typename S>ostream &operator<<(ostream &os, const map<T, S> &mp);template <typename T> ostream &operator<<(ostream &os, const set<T> &st);template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);template <typename T> ostream &operator<<(ostream &os, queue<T> q);template <typename T> ostream &operator<<(ostream &os, deque<T> q);template <typename T> ostream &operator<<(ostream &os, stack<T> st);template <class T, class Container, class Compare>ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);// --- END TOC ---// ---------------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>istream &operator>>(istream &is, pair<T1, T2> &p) {is >> p.first >> p.second;return is;}template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) {os << "[";for (int i = 0; i < (int)v.size(); i++) {os << v[i] << (i + 1 != (int)v.size() ? ", " : "]");}return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &v) {for (int i = 0; i < (int)v.size(); i++) {os << v[i] << endl;}return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) {for (int i = 0; i < (int)v.size(); i++) {os << "i = " << i << endl;os << v[i];}return os;}template <typename T> istream &operator>>(istream &is, vector<T> &v) {for (T &in : v)is >> in;return is;}template <typename T, typename S>ostream &operator<<(ostream &os, const map<T, S> &mp) {for (auto &[key, val] : mp) {os << key << ":" << val << " ";}return os;}template <typename T> ostream &operator<<(ostream &os, const set<T> &st) {os << "{";auto itr = st.begin();for (int i = 0; i < (int)st.size(); i++) {os << *itr << (i + 1 != (int)st.size() ? ", " : "}");itr++;}return os;}template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) {auto itr = st.begin();for (int i = 0; i < (int)st.size(); i++) {os << *itr << (i + 1 != (int)st.size() ? " " : "");itr++;}return os;}template <typename T> ostream &operator<<(ostream &os, queue<T> q) {while (q.size()) {os << q.front() << " ";q.pop();}return os;}template <typename T> ostream &operator<<(ostream &os, deque<T> q) {while (q.size()) {os << q.front() << " ";q.pop_front();}return os;}template <typename T> ostream &operator<<(ostream &os, stack<T> st) {while (st.size()) {os << st.top() << " ";st.pop();}return os;}template <class T, class Container, class Compare>ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) {while (pq.size()) {os << pq.top() << " ";pq.pop();}return os;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/util.hpp"#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/util.hpp"// --- Utils ---// 二分探索template <typename T>inline T bin_search(T ok, T ng, const function<bool(T)> is_ok) {assert(is_ok(ok));assert(!is_ok(ng));assert(ok < ng);while (abs(ok - ng) > 1) {T mid = (ok + ng) / 2;if (is_ok(mid))ok = mid;elseng = mid;}return ok;}// 順列全探索inline void rep_perm(int n, function<void(vec<int> &)> f) {vec<int> v(n);iota(v.begin(), v.end(), 0);do {f(v);} while (next_permutation(v.begin(), v.end()));}inline void rep_bit(int n, function<void(int)> f) { rep(i, 1LL << n) f(i); }// 配列 to stringtemplate <typename T> inline string join(const vec<T> &v, string sep = " ") {string res = "";rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep);return res;}template <typename T>inline void join_out(ostream &os, const vec<T> &v, string sep = " ",string end = "\n") {int n = v.size();rep(i, n) os << v[i] << (i == n - 1 ? end : sep);}template <typename T>inline void transform(vec<T> &src, function<void(T &)> f) {for (auto &val : src)f(val);}// ベース指定ceilinline ll ceil(ll x, ll base) { return (x + base - 1) / base * base; }// ベース指定floorinline ll floor(ll x, ll base) { return x / base * base; }// 合計値を求める// ll sum(const vec<ll> &v) { return accumulate(all(v), 0LL); }template <addable T> T sum(const vec<T> &v) { return accumulate(all(v), T()); }// 可変引数mintemplate <class... T> auto min(T... a) {return min(initializer_list<common_type_t<T...>>{a...});}// 可変引数maxtemplate <class... T> auto max(T... a) {return max(initializer_list<common_type_t<T...>>{a...});}template <class T> bool chmax(T &a, const T &b) {if (a < b) {a = b;return 1;}return 0;}template <class T> bool chmin(T &a, const T &b) {if (b < a) {a = b;return 1;}return 0;}// 3項間不等式// 広義単調増加inline bool is_increasing(int x, int y, int z) { return x <= y && y <= z; }// 半開区間[x, z)にyが含まれるか?inline bool is_contained(int x, int y, int z) { return x <= y && y < z; }// 頂点(x, y)が範囲に含まれるかinline bool is_contained(int H, int W, int x, int y) {return is_contained(0, x, H) && is_contained(0, y, W);}// rootに対し、aとbが同じ側にあるか (=は含まない)inline bool is_same_side(int root, int a, int b) {return (root < a) == (root < b);}// vector継承にする?template <typename T> struct vec_accumulate : public vec<T> {explicit vec_accumulate(vec<T> &v) : vec<T>(v.size()) {assert(v.size() > 0);this->at(0) = v[0];for (int i = 1; i < v.size(); ++i)this->at(i) = this->at(i - 1) + v[i];}// [0, i]の和// なので、-1 <= i < size()T operator[](int i) {assert(is_contained(-1, i, this->size()));if (i == -1)return T();return this->at(i);}};// vector functemplate <typename T> inline void unique_erase(vec<T> &v) {sort(all(v));v.erase(unique(all(v)), v.end());}void io_setup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << std::fixed << std::setprecision(15);}#line 12 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/pow.hpp"#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/pow.hpp"// 繰り返し2乗法template <integral T, integral F> constexpr T pow(T a, F n) {T ans = 1;while (n > 0) {if (n & 1)ans *= a;a *= a;n >>= 1;}return ans;}constexpr ll powm(ll a, ll n, const ll mod) {lll ans = 1;while (n > 0) {if (n & 1)ans = ans * a % mod;a = ((lll)a) * a % mod;n >>= 1;}return ans;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/all.hpp"#line 3 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/point.hpp"class Point {public:int x, y;Point() : x(0), y(0) {}Point(int x, int y) : x(x), y(y) {}Point up() const { return Point(x - 1, y); }Point down() const { return Point(x + 1, y); }Point left() const { return Point(x, y - 1); }Point right() const { return Point(x, y + 1); }Point upper_left() const { return Point(x - 1, y - 1); }Point upper_right() const { return Point(x - 1, y + 1); }Point lower_left() const { return Point(x + 1, y - 1); }Point lower_right() const { return Point(x + 1, y + 1); }vec<Point> around4() const { return {up(), down(), left(), right()}; }vec<Point> around8() const {return {up(), up().right(), right(), right().down(),down(), down().left(), left(), left().up()};}int manhattan() const { return std::abs(x) + std::abs(y); }int eucurid2() const { return x * x + y * y; }bool operator==(const Point &p) const { return x == p.x && y == p.y; }bool operator!=(const Point &p) const { return !(*this == p); }void operator+=(const Point &p) {x += p.x;y += p.y;}void operator-=(const Point &p) {x -= p.x;y -= p.y;}Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }bool operator<(const Point &p) const {return x == p.x ? y < p.y : x < p.x;}bool operator>(const Point &p) const {return x == p.x ? y > p.y : x > p.x;}};ostream &operator<<(ostream &os, const Point &p) {os << p.x << p.y;return os;}istream &operator>>(istream &is, Point &p) {is >> p.x >> p.y;return is;}inline bool is_contained(int H, int W, Point p) {return is_contained(H, W, p.x, p.y);}#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/area.hpp"class Area {public:int H, W;bool allow_outside = false;char out_val;Area(int H, int W) : H(H), W(W), data(vector(H, string(W, '.'))) {}Area(int H, int W, char out_val): H(H), W(W), data(vector(H, string(W, '.'))), allow_outside(true),out_val(out_val) {}string &operator[](int i) { return data[i]; }// 時計回りで90度回転Area rotated90() const {Area ret(W, H);rep(i, H) rep(j, W) ret[j][H - i - 1] = data[i][j];return ret;}void rotate90() {assert(H == W);data = rotated90().data;}char at(int x, int y) {if (is_contained(H, W, x, y))return data[x][y];else if (allow_outside)return out_val;else {cerr << "[Area::at] out of range" << endl;assert(false);}}void set(int x, int y, char val) {if (is_contained(H, W, x, y))data[x][y] = val;else if (allow_outside)return;else {cerr << "[Area::set] out of range" << endl;assert(false);}}bool contains(int x, int y) const { return is_contained(H, W, x, y); }bool contains(Point p) const { return is_contained(H, W, p.x, p.y); }private:vec<string> data;};ostream &operator<<(ostream &os, Area &a) {rep(i, a.H) os << a[i] << endl;return os;}istream &operator>>(istream &is, Area &a) {rep(i, a.H) is >> a[i];return is;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/rect.hpp"class Rect {public:int x, y, w, h;Rect(int x, int y, int w, int h) : x(x), y(y), w(w), h(h) {}int area() const { return w * h; }};#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/3d/all.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/3d/cuboid.hpp"class Cuboid {public:int x, y, z;int w, h, d;Cuboid(int x, int y, int z, int w, int h, int d): x(x), y(y), z(z), w(w), h(h), d(d) {}Cuboid(int w, int h, int d) : x(0), y(0), z(0), w(w), h(h), d(d) {}int volume() { return w * h * d; }Cuboid intersect(Cuboid c) {int x1 = max(x, c.x);int y1 = max(y, c.y);int z1 = max(z, c.z);int x2 = min(x + w, c.x + c.w);int y2 = min(y + h, c.y + c.h);int z2 = min(z + d, c.z + c.d);if (x2 <= x1 || y2 <= y1 || z2 <= z1) {return Cuboid(0, 0, 0, 0, 0, 0);}return Cuboid(x1, y1, z1, x2 - x1, y2 - y1, z2 - z1);}void move(int dx, int dy, int dz) {x += dx;y += dy;z += dz;}static Cuboid intersect(Cuboid &a, Cuboid &b) { return a.intersect(b); }static Cuboid intersect(initializer_list<Cuboid> cuboids) {auto it = cuboids.begin();Cuboid c = *it;it++;for (; it != cuboids.end(); it++) {c = c.intersect(*it);}return c;}};#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/convolution/all.hpp"// #include "convolution.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/comp.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/comp.hpp"// https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/4/DSL_4_Atemplate <typename T> struct comp {private:const int _n;int _cmp_n;vec<T> _raw, _comp;public:explicit comp(const vec<T> &src): _n(src.size()), _cmp_n(0), _raw(src), _comp(_n, 0) {sort(_raw.begin(), _raw.end());_raw.erase(unique(_raw.begin(), _raw.end()), _raw.end());_cmp_n = _raw.size();rep(i, _n) _comp[i] =lower_bound(_raw.begin(), _raw.end(), src[i]) - _raw.begin();}inline int size() const { return _n; }inline int cmp_size() const { return _cmp_n; }inline T get_raw(int complessed) {assert(0 <= complessed && complessed < _cmp_n);return _raw[complessed];}inline T operator[](int i) {assert(0 <= i && i < _n);return _comp[i];}inline T get_comp(int raw) {return lower_bound(_raw.begin(), _raw.end(), raw) - _raw.begin();}};#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/fenwick-tree.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/fenwick-tree.hpp"template <typename T> struct FenwickTree {private:T _n;vec<T> _data;public:explicit FenwickTree(T n) : _n(n), _data(n + 1, 0) {}explicit FenwickTree(const vec<T> &src) : _n(src.size()), _data(_n + 1, 0) {rep(i, _n) add(i, src[i]);}void add(int i, T val) {i++;while (i <= _n) {_data[i] += val;i += i & -i;}}// [0, i]int sum(int i) const {i++;T ans = 0;while (i > 0) {ans += _data[i];i -= i & -i;}return ans;}// [l, r)int sum(int l, int r) const { return sum(r - 1) - sum(l - 1); }};#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos.hpp"template <typename T> struct imos {private:const int _n;vec<T> _data;bool _is_build = false;public:explicit imos(int n) : _n(n), _data(_n + 1, 0) {}explicit imos(vec<T> src) : _n(src.size()), _data(_n + 1, 0) {rep(i, _n) add(i, src[i]);}inline int size() const { return _n; }inline void add(int l, int r, T x) {assert(!_is_build);assert(l < r);assert(0 <= l && r <= _n);_data[l] += x;_data[r] -= x;}inline void add(int i, T x) {assert(!_is_build);assert(0 <= i && i < _n);add(i, i + 1, x);}inline void build() {rep(i, _n) _data[i + 1] += _data[i];_is_build = true;}inline T get(int i) {assert(0 <= i && i < _n);if (!_is_build)build();return _data[i];}friend ostream &operator<<(ostream &os, const imos<T> &a) {if (!a._is_build) {os << "not builded";return os;}os << a._data;return os;}};#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos2d.hpp"#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos2d.hpp"template <typename T> struct imos2d {private:const int _H, _W;vvec<T> _data;bool _is_build = false;public:explicit imos2d(int H, int W): _H(H), _W(W), _data(_H + 1, vec<T>(_W + 1, 0)) {}explicit imos2d(vvec<T> src): _H(src.size()), _W(src[0].size()), _data(_H + 1, vec<T>(_W + 1, 0)) {rep(x, _H) rep(y, _W) add({x, y}, src[x][y]);}inline pair<int, int> size() const { return {_H, _W}; }// 半開区間inline void add(Point a, Point b, T x) {assert(!_is_build);assert(a.x < b.x && a.y < b.y);assert(is_contained(_H, _W, a) && is_contained(_H, _W, b.upper_left()));_data[a.x][a.y] += x;_data[a.x][b.y] -= x;_data[b.x][a.y] -= x;_data[b.x][b.y] += x;}inline void add(Point a, T x) {assert(!_is_build);assert(is_contained(_H, _W, a));add(a, a.lower_right(), x);}inline void build() {rep(x, _H) rep(y, _W) _data[x][y + 1] += _data[x][y];rep(y, _W) rep(x, _H) _data[x + 1][y] += _data[x][y];_is_build = true;}inline T get(Point p) const {assert(is_contained(_H, _W, p));assert(_is_build);return _data[p.x][p.y];}};template <typename T> ostream &operator<<(ostream &os, const imos2d<T> &im) {rep(x, im.size().first) {rep(y, im.size().second) { os << im.get({x, y}) << " "; }os << endl;}return os;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/lazy-segment-tree.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/monoid/monofunc.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/monoid/monoid.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/monoid/monoid.hpp"/*template <class M>concept MonoidConcept = requires(M &x, M::T a, M::T b) {typename M::T;{ M::e() } -> std::same_as<typename M::T>;{ M::op(a, b) } -> std::same_as<typename M::T>;};*/template <class Type> class Monoid {public:Monoid() = default;using T = Type;virtual T e() const = 0;virtual T op(T a, T b) const = 0;};template <class M>concept MonoidConcept = requires(M &x, typename M::T a, typename M::T b) {// derived_from<M, Monoid<typename M::T>>;typename M::T;{ x.e() } -> std::same_as<typename M::T>;{ x.op(a, b) } -> std::same_as<typename M::T>;};#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/monoid/monofunc.hpp"template <class Type, MonoidConcept Mono> class Monofunc {public:Monofunc() = default;using T = Type;using M = Mono;using MT = typename M::T;virtual T id() const = 0;virtual MT apply(T a, MT b) const = 0;virtual T merge(T before, T after) const = 0;};template <class M>concept MonofuncConcept = requires(M &x, typename M::T before,typename M::T after, typename M::MT mono) {typename M::T;typename M::M;typename M::MT;{ x.id() } -> std::same_as<typename M::T>;{ x.apply(before, mono) } -> std::same_as<typename M::MT>;{ x.merge(before, after) } -> std::same_as<typename M::T>;};#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/lazy-segment-tree.hpp"// 参考 https://qiita.com/ningenMe/items/bf66de877e3b97d35862// T : Nodeの型, F : 操作情報template <MonofuncConcept F> struct LazySegmentTree {private:using M = typename F::M;using FT = typename F::T;using MT = typename M::T;// 単位元 デフォルトでは、min(a, e) = min(e, a) = aconst MT e;const FT id;// Monoidsconst M _monoid;const F _monofunc;// 演算// const function<T(T, T)> op;// const function<T(F, T)> update;// const function<F(F, F)> merge;// 要素数int32_t _n;int32_t _height;// SefTreeのデータvec<MT> _data;vec<FT> _lazy;// 自分の遅延を解消して子に伝搬するinline void eval(int32_t k) {if (_lazy[k] == id)return;_data[k] = _monofunc.apply(_lazy[k], _data[k]);if (k < _n) {_lazy[k << 1 | 0] = _monofunc.merge(_lazy[k << 1 | 0], _lazy[k]);_lazy[k << 1 | 1] = _monofunc.merge(_lazy[k << 1 | 1], _lazy[k]);}_lazy[k] = id;}public:// n: 要素数, e: 単位元, id: 操作情報の単位元, op: 演算, update:// ノードの更新(fn,val->val), merge:// 操作aがすでに行われている状態に操作bを適用したときの操作// TODO: 2つの実装が別れているのをどうにかするexplicit inline LazySegmentTree(const int32_t n): _monoid(M()), _monofunc(F()), e(_monoid.e()), id(_monofunc.id()) {_n = 1;_height = 1;while (_n < n)_n <<= 1, _height++;_data = vec<MT>(_n << 1, e);_lazy = vec<FT>(_n << 1, id);}explicit inline LazySegmentTree(vec<MT> &data): _monoid(M()), _monofunc(F()), e(_monoid.e()), id(_monofunc.id()) {_n = 1;_height = 1;while (_n < data.size())_n <<= 1, _height++;_data = vec<MT>(_n << 1, e);_lazy = vec<FT>(_n << 1, id);rep(i, data.size()) _data[i + _n] = data[i];for (int i = _n - 1; i > 0; --i)_data[i] = _monoid.op(_data[i << 1], _data[i << 1 | 1]);}/*inline LazySegmentTree(const T e, const F id,const function<T(T, T)> op,const function<T(F, T)> update,const function<F(F, F)> merge,vec<T> &v): e(e), id(id), op(op), update(update), merge(merge) {_n = 1;_height = 1;while (_n < v.size())_n <<= 1, _height++;_data.resize(_n << 1, e);for(int i=0; i<v.size(); ++i) _data[i + _n] = v[i];_lazy = vec<F>(_n << 1, id);}*/inline void set(int32_t l, int32_t r, FT f) {/*eval(k);if (l <= a && b <= r) { // 完全に内側_lazy[k] = merge(f, _lazy[k]);eval(k);} else if (a < r && l < b) { // 一部区間が被る_set(l, r, f, (k << 1) + 1, a, (a + b) >> 1);_set(l, r, f, (k << 1) + 2, (a + b) >> 1, b);_data[k] = op(_data[(k << 1) + 1], _data[(k << 1) + 2]);}*/// a, bはseg-index [a,b]int32_t a = l + _n, b = r + _n - 1;// 上から下へとlazyを伝搬させるfor (int32_t i = _height; 0 < i; --i)eval(a >> i), eval(b >> i);// bを [a, b]から[a, b)にするfor (b++; a < b; a >>= 1, b >>= 1) {if (a & 1)_lazy[a] = _monofunc.merge(_lazy[a], f), eval(a), a++;if (b & 1)--b, _lazy[b] = _monofunc.merge(_lazy[b], f), eval(b);}// a, bをseg-index [a,b]に戻すa = l + _n, b = r + _n - 1;// a,bを親に移しつつ、aが実在頂点の間while ((a >>= 1), (b >>= 1), a) {if (_lazy[a] == id) {// _data[(a << 1) | 0] = update(_lazy[(a << 1) | 0], _data[(a << 1) |// 0]); _data[(a << 1) | 1] = update(_lazy[(a << 1) | 1], _data[(a << 1)// | 1]); _data[a] = op(_data[(a << 1) | 0], _data[(a << 1) | 1]);_data[a] = _monoid.op(_monofunc.apply(_lazy[(a << 1) | 0], _data[(a << 1) | 0]),_monofunc.apply(_lazy[(a << 1) | 1], _data[(a << 1) | 1]));}if (_lazy[b] == id) {// _data[(b << 1) | 0] = update(_lazy[(b << 1) | 0], _data[(b << 1) |// 0]); _data[(b << 1) | 1] = update(_lazy[(b << 1) | 1], _data[(b << 1)// | 1]); _data[b] = op(_data[(b << 1) | 0], _data[(b << 1) | 1]);_data[b] = _monoid.op(_monofunc.apply(_lazy[(b << 1) | 0], _data[(b << 1) | 0]),_monofunc.apply(_lazy[(b << 1) | 1], _data[(b << 1) | 1]));}}}// [l, r)の区間に対するクエリを処理する// kはSegTree上のindexinline MT query(int32_t l, int32_t r) {// ↓再帰/*eval(k);if (r <= a || b <= l)return e;if (l <= a && b <= r)return _data[k];T l_val = _query(l, r, (k << 1) + 1, a, (a + b) >> 1);T r_val = _query(l, r, (k << 1) + 2, (a + b) >> 1, b);return op(l_val, r_val);*/// a, bはseg-index [a,b]int32_t a = l + _n, b = r + _n - 1;// 上から下へとlazyを伝搬させるfor (int32_t i = _height; 0 <= i; --i)eval(a >> i), eval(b >> i);// line_debug();// printd(_data);// printd(_lazy);MT vl = e, vr = e;// bを [a, b]から[a, b)にするfor (b++; a < b; a >>= 1, b >>= 1) {if (a & 1)vl = _monoid.op(vl, _monofunc.apply(_lazy[a], _data[a])), a++;if (b & 1)b--, vr = _monoid.op(_monofunc.apply(_lazy[b], _data[b]), vr);}return _monoid.op(vl, vr);}inline MT get(int32_t i) { return query(i, i + 1); }};/*template <typename T, typename F> using LazySegtree = LazySegmentTree<T, F>;template <typename T, typename F> inline LazySegtree<T, F> RMQLazySeg(int n) {return LazySegmentTree<T, F>(n, numeric_limits<T>::max(), 0, [](T a, T b) { return min(a, b); },[](F a, T b) { return b + a; }, [](F a, F b) { return b + a; });}*/#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/segment-tree.hpp"#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/segment-tree.hpp"// 参考: https://qiita.com/ningenMe/items/bf66de877e3b97d35862template <MonoidConcept M> struct SegmentTree {using T = typename M::T;private:M _monoid;T e;// 要素数int _n;// SegTreeのノード上のデータvec<T> _data;public:explicit SegmentTree(int n) : _n(1), _monoid(M()), e(_monoid.e()) {while (_n < n)_n *= 2;_data = vec<T>(2 * _n, e);}explicit SegmentTree(const vec<T> &v) : _n(1), _monoid(M()), e(_monoid.e()) {while (_n < v.size())_n *= 2;_data = vec<T>(2 * _n, e);rep(i, v.size()) _data[i + _n] = v[i];for (int i = _n - 1; i > 0; --i)_data[i] = _monoid.op(_data[i << 1], _data[i << 1 | 1]);}void set(int i, T a) {// 1段目は1, 2段目は2~3, ... , 最下段はn~(2n-1)// より、iの最下段はi+ni += _n;_data[i] = a;// i >>= 1で、iを親のindexに変更// また、i==0となってしまうなら、i==1(頂点)であるので、終了// i<<1は、(更新後の)iの左の子// i<<1|1は、(更新後の)iの右の子 (+1を|1で表現)while (i >>= 1)_data[i] = _monoid.op(_data[i << 1], _data[i << 1 | 1]);}T get(int i) const { return _data[i + _n]; }T query(int l, int r) {T l_val = e, r_val = e;// l, r(index)に+_nすると、最下段のseg-indexになる// l < r == l,rをすべて含む区間にはたどり着いていない// l/r >>= 1 : l/rを親に移動させるfor (l += _n, r += _n; l < r; l >>= 1, r >>= 1) {// lが左の子ならば、l<=iの結果はlの親の結果であるので、計算しない// lが右の子ならば、計算する必要があるif (l & 1)l_val = _monoid.op(l_val, _data[l++]);// l++をしても、l>>1が変わることはない// ただし、r=l+1のとき、答えはここのlである// ので、l<rに引っかかるようにして終了させている?// rが左の子ならば、rの親はギリギリ使われない、すなわちrの条件を満たす// rが右の子ならば、r-1は範囲に含まれるので、計算する必要があるif (r & 1)r_val = _monoid.op(_data[--r], r_val);}return _monoid.op(l_val, r_val);}};#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/union-find.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/union-find.hpp"struct UnionFind {private:int _n;vec<int> _parents;vec<int> _size;public:explicit UnionFind(int n) : _n(n), _parents(n), _size(n, 1) {iota(all(_parents), 0);}int find(int a) {if (_parents[a] == a)return a;elsereturn _parents[a] = find(_parents[a]);}void merge(int a, int b) {a = find(a);b = find(b);if (a != b) {// merge後の親はaif (_size[a] < _size[b])swap(a, b);_size[a] += _size[b];_size[b] = 0;_parents[b] = a;}}int size(int a) { return _size[find(a)]; }bool same(int a, int b) { return find(a) == find(b); }vec<vec<int>> groups() {vec<int> leaders(_n);rep(i, _n) { leaders[i] = find(i); }vec<vec<int>> res(_n);rep(i, _n) res[i].reserve(_size[i]);rep(i, _n) res[leaders[i]].push_back(i);res.erase(remove_if(all(res), [&](const vec<int> &v) { return v.empty(); }),res.end());return res;}};using UF = UnionFind;#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/weighted-union-find.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/weighted-union-find.hpp"template <addable T> struct WeightedUnionFind {private:int _n;vec<int> _parents;vec<int> _size;vec<T> _weight;T weight(int i) {find(i);return _weight[i];}public:explicit WeightedUnionFind(int n): _n(n), _parents(n), _size(n, 1), _weight(n) {iota(all(_parents), 0);}int find(int i) {if (_parents[i] == i)return i;const int root = find(_parents[i]);_weight[i] += _weight[_parents[i]];return _parents[i] = root;}void merge(int a, int b, T w) {w += weight(a);w -= weight(b);a = find(a);b = find(b);if (a != b) {// merge後の親はaif (_size[a] < _size[b])swap(a, b), w = -w;_size[a] += _size[b];_size[b] = 0;_parents[b] = a;_weight[b] = w;}}T diff(int a, int b) { return weight(b) - weight(a); }int size(int a) { return _size[find(a)]; }bool same(int a, int b) { return find(a) == find(b); }};template <addable T> using WUF = WeightedUnionFind<T>;#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/cycle.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/template.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/template.hpp"// Nodetemplate <class T = ll> struct WeightedNode {int id;T cost = numeric_limits<T>::max();WeightedNode(int id, T cost) : id(id), cost(cost) {}};struct WeightState {public:int location;ll used_cost;WeightState(int location, ll used_cost): location(location), used_cost(used_cost) {}bool operator<(const WeightState &n) const { return used_cost < n.used_cost; }bool operator>(const WeightState &n) const { return used_cost > n.used_cost; }};// Graphstruct Graph {private:const int n;const bool directed;vec<vec<int>> edges;public:explicit Graph(int n, bool directed = false): n(n), directed(directed), edges(n) {}inline void add_edge(int u, int v) {edges[u].emplace_back(v);if (!directed)edges[v].emplace_back(u);}inline vec<int> &operator[](int i) { return edges[i]; }inline int size() const { return n; }};template <class T = ll> struct WeightedGraph {private:const int n;const bool directed;vec<vec<WeightedNode<T>>> edges;public:explicit WeightedGraph(int n, bool directed = false): n(n), directed(directed), edges(n) {}inline void add_edge(int u, int v, T w) {edges[u].emplace_back(WeightedNode(v, w));if (!directed)edges[v].emplace_back(WeightedNode(u, w));}inline vec<WeightedNode<T>> &operator[](int i) { return edges[i]; }inline int size() const { return n; }};// template <class T = ll> using WeightedGraph = vec<vec<WeightedNode<T>>>;template <class T = ll> using WGraph = WeightedGraph<T>;#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/cycle.hpp"bool has_cycle(Graph &g, int start = 0) {vec<int> seen(g.size(), 0);vec<int> finished(g.size(), 0);auto dfs = [&](auto fn, int index) {seen[index] = 1;for (auto next : g[index]) {if (finished[next])continue;if (seen[next] && !finished[next])return true;if (fn(fn, next))return true;}finished[index] = 1;return false;};return dfs(dfs, start);}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/depth.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/depth.hpp"struct TreeNodeInfo {public:TreeNodeInfo(int parent, int depth) : parent(parent), depth(depth) {}int parent;int depth;};vec<TreeNodeInfo> depth(Graph &graph, int root = 0) {vec<TreeNodeInfo> result(graph.size(), TreeNodeInfo(-1, -1));stack<int> st;st.push(root);result[root] = TreeNodeInfo(root, 0);while (!st.empty()) {int index = st.top();st.pop();for (auto next : graph[index]) {if (result[next].depth != -1)continue;result[next] = TreeNodeInfo(index, result[index].depth + 1);st.push(next);}}return result;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/diameter.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/diameter.hpp"int diameter(Graph &graph, int start = 0) {vec<int> seen(graph.size(), 0);auto dfs = [&](auto fn, int index) -> pair<int, int> {// max-cost, indexpair<int, int> result = {0, index};seen[index] = 1;for (auto next : graph[index]) {if (seen[next])continue;auto next_result = fn(fn, next);next_result.first += 1;result = max(result, next_result);}seen[index] = 0;return result;};auto result = dfs(dfs, start);result = dfs(dfs, result.second);return result.first;}template <typename T = ll> int diameter(WGraph<T> &graph, int start = 0) {auto dfs = [&](int index) -> pair<T, int> {vec<T> result(graph.size(), -1);T mx = 0;int mx_index = index;stack<int> st;st.push(index);result[index] = 0;while (!st.empty()) {int current = st.top();st.pop();for (auto next : graph[current]) {if (result[next.id] >= 0)continue;st.push(next.id);result[next.id] = result[current] + next.cost;if (chmax(mx, result[next.id])) {mx_index = next.id;}}}return {mx, mx_index};};auto result = dfs(start);result = dfs(result.second);return result.first;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/dijkstra.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/dijkstra.hpp"template <typename T = ll> vec<ll> dijkstra(WGraph<T> &graph, int start) {vec<ll> way(graph.size(), INF);rp_queue<WeightState> q;q.push(WeightState(start, 0));way[start] = 0;while (!q.empty()) {WeightState current = q.top();q.pop();for (auto &next : graph[current.location]) {ll next_cost = current.used_cost + next.cost;if (way[next.id] <= next_cost)continue;way[next.id] = next_cost;q.push(WeightState(next.id, way[next.id]));}}return way;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/lca.hpp"struct LCA {private:Graph graph;int root;// parent[k][v] := vの2^k先の親vec<vec<int>> parent;vec<TreeNodeInfo> depth_data;public:explicit LCA(Graph &graph, int root = 0): graph(graph), root(root), depth_data(depth(graph, root)) {int n = graph.size();int logn = 1;while ((1 << logn) < n)logn++;parent = vector(logn, vector(n, -1LL));for (int i = 0; i < n; i++)parent[0][i] = depth_data[i].parent;// ダブリングfor (int k = 0; k + 1 < logn; k++) {for (int i = 0; i < n; i++) {if (parent[k][i] < 0)parent[k + 1][i] = -1;elseparent[k + 1][i] = parent[k][parent[k][i]];}}}int query(int u, int v) const {if (depth_data[u].depth > depth_data[v].depth)swap(u, v);int logn = parent.size();// uとvの深さが同じになるまで親を辿るrep(k, logn) {if ((depth_data[v].depth - depth_data[u].depth) >> k & 1) {v = parent[k][v];}}// にぶたんif (u == v)return u;for (int k = logn - 1; k >= 0; k--) {if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}}return parent[0][u];}};#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/topological-sort.hpp"#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/topological-sort.hpp"vec<int> topological_sort(Graph &graph) {vec<int> result;vec<int> deleted(graph.size(), false);vec<int> in_count(graph.size());rep(i, graph.size()) {for (auto next : graph[i]) {in_count[next]++;}}queue<int> q;rep(i, graph.size()) {if (in_count[i] == 0) {q.push(i);}}while (!q.empty()) {int now = q.front();q.pop();result.emplace_back(now);deleted[now] = true;for (auto next : graph[now]) {if (deleted[next])continue;in_count[next]--;if (in_count[next] == 0) {q.push(next);}}}return result;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp"// #include "combination.hpp"// #include "factorial.hpp"#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/modint.hpp"#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/modint.hpp"namespace modint_utils {constexpr inline int32_t normalize(int val, int32_t mod) {return (val % mod + mod) % mod;}constexpr inline int32_t inv(int32_t a, int32_t mod) {int32_t b = mod, u = 1, v = 0;while (b) {int32_t t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}u %= mod;if (u < 0)u += mod;return u;// return mod_pow(val, mod - 2, mod);}} // namespace modint_utilstemplate <int MOD> struct dynamic_modint {private:int _val;public:dynamic_modint() : dynamic_modint(0) {}dynamic_modint(int val) : _val(modint_utils::normalize(val, MOD)) {}// logicint val() const { return _val; }inline dynamic_modint inv() const {return dynamic_modint(modint_utils::inv(_val, MOD));}inline dynamic_modint pow(const int n) const {return dynamic_modint(powm(_val, n, MOD));}inline static constexpr dynamic_modint pow(const dynamic_modint &a,const int n) {return dynamic_modint(mod_pow(a._val, n, a.MOD));}// opinline dynamic_modint &operator++() { return *this += 1; }inline dynamic_modint &operator--() { return *this -= 1; }inline dynamic_modint operator++(int32_t) const {dynamic_modint tmp = *this;++*this;return tmp;}inline dynamic_modint operator--(int32_t) {dynamic_modint tmp = *this;--*this;return tmp;}inline dynamic_modint operator+(const dynamic_modint &a) const {return dynamic_modint(_val) += a;}inline dynamic_modint operator-(const dynamic_modint &a) const {return dynamic_modint(_val) -= a;}inline dynamic_modint operator*(const dynamic_modint &a) const {return dynamic_modint(_val) *= a;}inline dynamic_modint operator/(const dynamic_modint &a) const {return dynamic_modint(_val) /= a;}inline bool operator==(const dynamic_modint &a) { return _val == a._val; }inline bool operator!=(const dynamic_modint &a) { return _val != a._val; }inline dynamic_modint &operator+=(const dynamic_modint &a) {_val += a.val();if (_val >= MOD)_val -= MOD;return *this;}inline dynamic_modint &operator-=(const dynamic_modint &a) {_val -= a.val();if (_val < 0)_val += MOD;return *this;}inline dynamic_modint &operator*=(const dynamic_modint &a) {_val = _val * a.val() % MOD;return *this;}inline dynamic_modint &operator/=(const dynamic_modint &a) {*this *= modint_utils::inv(a.val(), MOD);return *this;}explicit operator int() const { return _val; }// iofriend ostream &operator<<(ostream &os, const dynamic_modint &a) {return os << a._val;}friend istream &operator>>(istream &os, dynamic_modint &a) {os >> a._val;a._val = modint_utils::normalize(a._val, MOD);return os;}};// using modint998 = modint<998244353>;template <int MOD>ostream &operator<<(ostream &os, const dynamic_modint<MOD> &i) {os << i.val();return os;}template <int MOD>ostream &operator<<(ostream &os, const vector<dynamic_modint<MOD>> &v) {for (int i = 0; i < (int)v.size(); i++) {os << v[i].val() << (i + 1 != (int)v.size() ? " " : "");}return os;}template <const int32_t MOD> struct modint {private:using i32 = int32_t;i32 _val;public:consteval inline modint() noexcept : _val(0) {}constexpr inline modint(int val) noexcept: _val(modint_utils::normalize(val, MOD)) {}constexpr inline modint(modint const &val) noexcept : _val(val._val) {}// logicconstexpr i32 val() const noexcept { return _val; }constexpr modint pow(const int n) const { return modint(powm(_val, n, MOD)); }constexpr inline static modint pow(const modint &a, const int n) noexcept {return modint(mod_pow(a._val, n, a.MOD));}constexpr inline modint inv() const noexcept {return modint(modint_utils::inv(_val, MOD));}// opconstexpr inline modint &operator++() noexcept { return *this += 1; }constexpr inline modint &operator--() noexcept { return *this -= 1; }constexpr inline modint operator++(int32_t) noexcept {modint tmp = *this;++*this;return tmp;}constexpr inline modint operator--(int32_t) noexcept {modint tmp = *this;--*this;return tmp;}constexpr inline modint operator+(const modint &a) const noexcept {return modint(*this) += a;}constexpr inline modint operator-(const modint &a) const noexcept {return modint(*this) -= a;}constexpr inline modint operator*(const modint &a) const noexcept {return modint(*this) *= a;}constexpr inline modint operator/(const modint &a) const noexcept {return modint(*this) /= a;}constexpr inline bool operator==(const modint &a) const noexcept {return _val == a.val();}constexpr inline bool operator!=(const modint &a) const noexcept {return _val != a.val();}constexpr inline modint &operator+=(const modint &a) noexcept {_val += a._val;if (_val >= MOD)_val -= MOD;return *this;}constexpr inline modint &operator-=(const modint &a) noexcept {_val -= a._val;if (_val < 0)_val += MOD;return *this;}constexpr inline modint &operator*=(const modint &a) noexcept {_val = (ll)_val * a._val % MOD;return *this;}constexpr inline modint &operator/=(const modint &a) noexcept {*this *= modint_utils::inv(a.val(), MOD);return *this;}explicit operator int() const noexcept { return _val; }// iofriend ostream &operator<<(ostream &os, const modint &a) noexcept {return os << a._val;}friend istream &operator>>(istream &os, modint &a) noexcept {os >> a._val;a._val = modint_utils::normalize(a._val, MOD);return os;}};using mint998 = modint<998244353>;#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/prime.hpp"#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/prime.hpp"// ミラーラビン素数判定法// O(k log^3 n)// https://drken1215.hatenablog.com/entry/2023/05/23/233000bool MillerRabin(long long N, vector<long long> A) {long long s = 0, d = N - 1;while (d % 2 == 0) {++s;d >>= 1;}for (auto a : A) {if (N <= a)return true;long long t, x = powm(a, d, N);if (x != 1) {for (t = 0; t < s; ++t) {if (x == N - 1)break;x = __int128_t(x) * x % N;}if (t == s)return false;}}return true;}bool is_prime(long long N) {if (N <= 1)return false;if (N == 2)return true;if (N % 2 == 0)return false;if (N < 4759123141LL)return MillerRabin(N, {2, 7, 61});elsereturn MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});}// ポラード・ロー素因数分解法// 値が大きい場合に有効、ちゃんと調べる!// O(n^(1/4))// https://lpha-z.hatenablog.com/entry/2023/01/15/231500// https://algo-method.com/tasks/553/editorialuint64_t pollard_rho(uint64_t N) {if (N % 2 == 0)return 2;if (is_prime(N))return N;uint64_t step = 0;auto f = [&](uint64_t x) -> uint64_t {return (__int128_t(x) * x + step) % N;};while (true) {++step;uint64_t x = step, y = f(x);while (true) {uint64_t p = gcd(y - x + N, N);if (p == 0 || p == N)break;if (p != 1)return p;x = f(x);y = f(f(y));}}}// 素因数分解// https://algo-method.com/tasks/553/editorialstruct PrimeFactor {uint64_t prime;uint64_t exp;};vec<PrimeFactor> prime_factorize(uint64_t N) {if (N == 1)return {};uint64_t p = pollard_rho(N);if (p == N)return {{p, 1}};auto left = prime_factorize(p);auto right = prime_factorize(N / p);left.insert(left.end(), all(right));sort(all(left), [](const PrimeFactor &a, const PrimeFactor &b) {return a.prime < b.prime;});vec<PrimeFactor> ans;rep(i, left.size()) {if (i == 0 || left[i].prime != left[i - 1].prime)ans.emplace_back(left[i]);elseans.back().exp += left[i].exp;}return ans;}#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/rational.hpp"template <typename T = ll> struct Rational {T num, den;Rational(T num) : num(num), den(1) {}Rational(T num, T den) : num(num), den(den) {T g = gcd(num, den);this->num /= g;this->den /= g;}Rational operator+(const Rational &rhs) const {return Rational(num * rhs.den + rhs.num * den, den * rhs.den);}Rational operator-(const Rational &rhs) const {return Rational(num * rhs.den - rhs.num * den, den * rhs.den);}Rational operator*(const Rational &rhs) const {return Rational(num * rhs.num, den * rhs.den);}Rational operator/(const Rational &rhs) const {return Rational(num * rhs.den, den * rhs.num);}bool operator<(const Rational &rhs) const {return num * rhs.den < rhs.num * den;}bool operator>(const Rational &rhs) const {return num * rhs.den > rhs.num * den;}bool operator==(const Rational &rhs) const {return num * rhs.den == rhs.num * den;}bool operator!=(const Rational &rhs) const { return !(*this == rhs); }bool operator<=(const Rational &rhs) const {return (*this < rhs) || (*this == rhs);}bool operator>=(const Rational &rhs) const {return (*this > rhs) || (*this == rhs);}friend ostream &operator<<(ostream &os, const Rational &r) {return os << r.num << "/" << r.den;}void operator+=(const Rational &rhs) { *this = *this + rhs; }void operator-=(const Rational &rhs) { *this = *this - rhs; }void operator*=(const Rational &rhs) { *this = *this * rhs; }void operator/=(const Rational &rhs) { *this = *this / rhs; }double val() const { return (double)num / den; }// operator double() const { return val(); }// operator string() const { return to_string(num) + "/" + to_string(den); }Rational pow(ll n) const {if (n == 0) {return Rational(1);} else if (n < 0) {return Rational(den, num).pow(-n);} else {Rational res = pow(n / 2);res *= res;if (n % 2 == 1) {res *= *this;}return res;}}};#line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"// #include "string/all.hpp"// #include "util/all.hpp"#line 3 "main.cpp"using mint = modint<998'244'353>;void solve() {int N;cin >> N;vec<string> S(N);cin >> S;set<string> st;rep(i, N) rep(j, N) {if(i == j) continue;st.insert(S[i] + S[j]);}cout << st.size() << endl;}void test() {}signed main() {io_setup();// inputsolve();// test();}