結果
| 問題 | No.2941 Sigma Music Game Score Problem |
| ユーザー |
 e6nlaq
|
| 提出日時 | 2024-10-18 22:45:55 |
| 言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 354 ms / 2,500 ms |
| コード長 | 54,936 bytes |
| コンパイル時間 | 4,473 ms |
| コンパイル使用メモリ | 306,372 KB |
| 実行使用メモリ | 11,136 KB |
| 最終ジャッジ日時 | 2024-10-18 22:54:42 |
| 合計ジャッジ時間 | 9,507 ms |
|
ジャッジサーバーID （参考情報） |
judge8 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,940 KB |
| testcase_04 | AC | 2 ms
6,940 KB |
| testcase_05 | AC | 2 ms
6,944 KB |
| testcase_06 | AC | 4 ms
6,944 KB |
| testcase_07 | AC | 2 ms
6,944 KB |
| testcase_08 | AC | 2 ms
6,940 KB |
| testcase_09 | AC | 3 ms
6,944 KB |
| testcase_10 | AC | 3 ms
6,944 KB |
| testcase_11 | AC | 3 ms
6,940 KB |
| testcase_12 | AC | 3 ms
6,940 KB |
| testcase_13 | AC | 4 ms
6,944 KB |
| testcase_14 | AC | 4 ms
6,944 KB |
| testcase_15 | AC | 3 ms
6,940 KB |
| testcase_16 | AC | 239 ms
8,988 KB |
| testcase_17 | AC | 267 ms
9,680 KB |
| testcase_18 | AC | 308 ms
10,836 KB |
| testcase_19 | AC | 249 ms
9,232 KB |
| testcase_20 | AC | 200 ms
8,132 KB |
| testcase_21 | AC | 88 ms
6,944 KB |
| testcase_22 | AC | 95 ms
6,940 KB |
| testcase_23 | AC | 88 ms
6,944 KB |
| testcase_24 | AC | 310 ms
10,968 KB |
| testcase_25 | AC | 37 ms
6,940 KB |
| testcase_26 | AC | 2 ms
6,944 KB |
| testcase_27 | AC | 2 ms
6,940 KB |
| testcase_28 | AC | 2 ms
6,940 KB |
| testcase_29 | AC | 104 ms
6,940 KB |
| testcase_30 | AC | 158 ms
8,224 KB |
| testcase_31 | AC | 328 ms
11,136 KB |
| testcase_32 | AC | 354 ms
11,116 KB |
ソースコード
/*------------------------------------------------------------
Welcome to my program!
PLEASE DON'T HACK ME...
∧＿∧ AtCoder / Codeforces / yukicoder etc
( ･ω･)
＿(__つ/￣￣￣ /
＼/ / C++ GCC 14.0.1
￣￣￣￣￣
Let's write Code!
------------------------------------------------------------*/
// Return Code 139(out_of_range)が出たら試す
// #define _GLIBCXX_DEBUG
/* #region AtCoder Template */
#include <bits/stdc++.h>
using namespace std;
// ローカル環境チェック
#if __has_include("./cpp-dump/cpp-dump.hpp")
#define LOCAL
#endif
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#include <utility>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n>
constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m>
constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T>
using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T>
using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T>
using is_modint = std::is_base_of<modint_base, T>;
template <class T>
using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)> * = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T> * = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T> * = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint &operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint &operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint &operator+=(const mint &rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint &operator-=(const mint &rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint &operator*=(const mint &rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint &lhs, const mint &rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint &lhs, const mint &rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint &lhs, const mint &rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint &lhs, const mint &rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint &lhs, const mint &rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint &lhs, const mint &rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id>
struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T> * = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T> * = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint &operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint &operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint &operator+=(const mint &rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint &operator-=(const mint &rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint &operator*=(const mint &rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint &lhs, const mint &rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint &lhs, const mint &rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint &lhs, const mint &rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint &lhs, const mint &rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint &lhs, const mint &rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint &lhs, const mint &rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id>
internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class>
struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
using namespace atcoder;
#ifdef LOCAL
#include "./cpp-dump/cpp-dump.hpp"
#ifdef ATCODER_MODINT_HPP
namespace cpp_dump::_detail {
template <int m>
inline std::string export_var(
const atcoder::static_modint<m> &mint, const std::string &indent, std::size_t last_line_length,
std::size_t current_depth, bool fail_on_newline, const export_command &command) {
return export_var(mint.val(), indent, last_line_length, current_depth, fail_on_newline, command);
}
template <int m>
inline std::string export_var(
const atcoder::dynamic_modint<m> &mint, const std::string &indent, std::size_t last_line_length,
std::size_t current_depth, bool fail_on_newline, const export_command &command) {
return export_var(mint.val(), indent, last_line_length, current_depth, fail_on_newline, command);
}
} // namespace cpp_dump::_detail
#endif
#define debug(...) cpp_dump(__VA_ARGS__)
CPP_DUMP_SET_OPTION_GLOBAL(log_label_func, cpp_dump::log_label::filename(true));
// 色数を増やす
CPP_DUMP_SET_OPTION_GLOBAL(es_value.log, "\x1b[02m"); // log: 灰色
CPP_DUMP_SET_OPTION_GLOBAL(es_value.expression, "\x1b[38;5;39m"); // reserved: 明るい青
CPP_DUMP_SET_OPTION_GLOBAL(es_value.reserved, "\x1b[34m"); // expression: 青
CPP_DUMP_SET_OPTION_GLOBAL(es_value.number, "\x1b[38;5;150m"); // number: 明るい緑
CPP_DUMP_SET_OPTION_GLOBAL(es_value.character, "\x1b[38;5;172m"); // character: オレンジ
CPP_DUMP_SET_OPTION_GLOBAL(es_value.escaped_char, "\x1b[38;5;220m"); // escaped_char: 明るいオレンジ
CPP_DUMP_SET_OPTION_GLOBAL(es_value.op, "\x1b[02m"); // op: 灰色
CPP_DUMP_SET_OPTION_GLOBAL(es_value.identifier, "\x1b[32m"); // identifier: 緑
CPP_DUMP_SET_OPTION_GLOBAL(es_value.member, "\x1b[96m"); // member: 明るいシアン
CPP_DUMP_SET_OPTION_GLOBAL(es_value.unsupported, "\x1b[31m"); // unsupported: 赤
CPP_DUMP_SET_OPTION_GLOBAL(es_value.bracket_by_depth, (std::vector<std::string>{
"\x1b[33m", // bracket_by_depth[0]: 黄色
"\x1b[35m", // bracket_by_depth[1]: マゼンタ
"\x1b[36m", // bracket_by_depth[2]: シアン
}));
CPP_DUMP_SET_OPTION_GLOBAL(es_value.class_op, "\x1b[02m"); // class_op: 灰色
CPP_DUMP_SET_OPTION_GLOBAL(es_value.member_op, "\x1b[02m"); // member_op: 灰色
CPP_DUMP_SET_OPTION_GLOBAL(es_value.number_op, ""); // number_op: デフォルト
// クラスやメンバ、数値の演算子(::, <>, (), -, +, etc...)に
// 色(class_op, member_op, number_op)を付ける
CPP_DUMP_SET_OPTION_GLOBAL(detailed_class_es, true);
CPP_DUMP_SET_OPTION_GLOBAL(detailed_member_es, true);
CPP_DUMP_SET_OPTION_GLOBAL(detailed_number_es, true);
namespace cp = cpp_dump;
auto _unnsedcpnamespaceunwarn = cp::options::es_value;
#else
#define debug(...)
#endif
// 高速化
#pragma GCC target("avx,avx2")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fastio \
cin.tie(nullptr); \
ios::sync_with_stdio(false); \
cout << fixed << setprecision(15); \
srand((unsigned)time(NULL));
// 型省略
using uint = unsigned;
using ll = long long;
// using ll = __int128_t;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vd = vector<double>;
using vld = vector<ld>;
using vull = vector<ull>;
using vpll = vector<pll>;
using pdd = pair<ld, ld>;
using psl = pair<string, ll>;
using pcl = pair<char, ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvc = vector<vc>;
using vvs = vector<vs>;
using vvb = vector<vb>;
using vvld = vector<vld>;
using vvd = vector<vd>;
using mll = map<ll, ll>;
using mcl = map<char, ll>;
using msl = map<string, ll>;
using sll = set<ll>;
using spll = set<pair<ll, ll>>;
using spdd = set<pair<ld, ld>>;
using stll = stack<ll>;
using qll = queue<ll>;
using qd = queue<ld>;
using qs = queue<string>;
using qc = queue<char>;
using int128_t = __int128_t;
template <typename Tp1, typename Tp2>
using unmap = unordered_map<Tp1, Tp2>;
template <typename Tp>
using unset = unordered_set<Tp>;
template <typename Tp>
using reverse_queue = priority_queue<Tp, vector<Tp>, greater<Tp>>;
template <typename T>
using vec2 = vector<vector<T>>;
template <typename T>
using vec3 = vector<vector<vector<T>>>;
#if __cplusplus >= 202002L
#define cpp20
template <typename T>
concept number = integral<T> || floating_point<T>;
#endif
// マクロ
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define irep(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define arep(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define adrep(i, a, d, n) for (ll i = (a); i < (ll)(n); i += d)
#define until(b) while (!(b))
// 省略define
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define endl "\n"
#define br break
#define el else
#define elif else if
template <typename T>
inline void YESNO(T b) {
cout << (b ? "YES" : "NO") << endl;
}
template <typename T>
inline void yesno(T b) {
cout << (b ? "yes" : "no") << endl;
}
template <typename T>
inline void YesNo(T b) {
cout << (b ? "Yes" : "No") << endl;
}
template <typename T, typename tr, typename fal>
inline void outif(T b, tr tru, fal fals) {
if (b) {
cout << tru << endl;
} else {
cout << fals << endl;
}
}
#define exit exit(0)
#define co(x) cout << (x) << endl
// 定数
const string sl = "";
constexpr char cl = '\0';
constexpr ll nl = 0LL;
constexpr ll INFINT = 2047483647;
constexpr ll INFLL = 1023372036854775807LL; // だいたい
const ll mod1 = pow(10, 9) + 1;
constexpr char sp = ' ';
const ll j2_32 = pow(2, 32);
const ll j2_m32 = pow(2, -32);
const ll j2_10 = pow(2, 10);
const vector<int> dx = {0, 0, 1, -1};
const vector<int> dy = {1, -1, 0, 0};
const vector<int> ex = {-1, -1, -1, 0, 0, 1, 1, 1};
const vector<int> ey = {-1, 0, 1, -1, 1, -1, 0, 1};
const string spa = " ";
constexpr bool except = true;
// 色々なテンプレ(完全コピペ)
template <class T>
size_t HashCombine(const size_t seed, const T &v) {
return seed ^ (std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}
/* pair用 */
template <class T, class S>
struct std::hash<std::pair<T, S>> {
size_t operator()(const std::pair<T, S> &keyval) const noexcept {
return HashCombine(std::hash<T>()(keyval.first), keyval.second);
}
};
/* vector用 */
template <class T>
struct std::hash<std::vector<T>> {
size_t operator()(const std::vector<T> &keyval) const noexcept {
size_t s = 0;
for (auto &&v : keyval)
s = HashCombine(s, v);
return s;
}
};
/* tuple用 */
template <int N>
struct HashTupleCore {
template <class Tuple>
size_t operator()(const Tuple &keyval) const noexcept {
size_t s = HashTupleCore<N - 1>()(keyval);
return HashCombine(s, std::get<N - 1>(keyval));
}
};
template <>
struct HashTupleCore<0> {
template <class Tuple>
size_t operator()(const Tuple &keyval) const noexcept { return 0; }
};
template <class... Args>
struct std::hash<std::tuple<Args...>> {
size_t operator()(const tuple<Args...> &keyval) const noexcept {
return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);
}
};
std::string
operator""_s(char const *str, std::size_t) {
return str;
}
std::string
operator*(std::string const &str, int n) {
if (n < 1)
return "";
std::string result;
result.reserve(str.length() * n);
for (int i = 0; i < n; ++i) {
result += str;
}
return result;
}
// https://kenkoooo.hatenablog.com/entry/2016/11/30/163533
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
__int128 parse(string &s) {
__int128 ret = 0;
for (ull i = 0; i < s.length(); i++)
if ('0' <= s[i] && s[i] <= '9')
ret = 10 * ret + s[i] - '0';
if (s[0] == '-') {
ret = -ret;
}
return ret;
}
istream &operator>>(std::istream &is, __int128_t &value) {
string tmp;
is >> tmp;
value = parse(tmp);
return is;
}
// 関数類
/**
* @brief 素数をチェックします
*
* @param num 判定する数値
* @return bool 素数かどうか
*/
inline bool isprime(const ull num) noexcept(except) {
if (num < 2)
return false;
else if (num == 2)
return true;
else if (num % 2 == 0)
return false;
double sqrtNum = sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2) {
if (num % i == 0) {
return false;
}
}
return true;
}
/**
* @brief char型の数値をint型に変換します
*
* @param c 変換する文字
* @return int 変換した数値
*/
inline int ctoi(const char c) noexcept(except) {
if (c >= '0' && c <= '9')
return c - '0';
return 0;
}
/**
* @brief 1+2+3+4+...n
*
* @param n
* @return int
*/
inline ull minisum(const ull n) noexcept(except) {
return n * (n + 1ULL) / 2ULL;
}
/**
* @brief 数値を桁数で0埋めします
*
* @tparam T 桁数の型
* @param i 桁数
* @param s 埋める文字列
* @return string 0埋め後の文字列
*/
inline string zerou(const ull i, string s) noexcept(except) {
while (s.size() != i)
s = '0' + s;
return s;
}
/**
* @brief T型をchar型に変換します
*
* @tparam T 変換する型
* @param i 変換する数値
* @return char 変換後の文字
*/
inline char to_char(const ull i) noexcept(except) {
assert(i <= 9);
return '0' + i;
}
/**
* @brief i < j の場合iをjで置き換えます
*
* @tparam T1_ iの型
* @tparam T2_ jの型
* @param i 上書きする変数
* @param j 比較する変数
* @return bool 置き換えたかどうか
*/
template <typename T1_, typename T2_>
inline bool chmax(T1_ &i, const T2_ j) noexcept(except) {
if (i < j) {
i = j;
return true;
}
return false;
}
/**
* @brief i > j の場合iをjで置き換えます
*
* @tparam T1_ iの型
* @tparam T2_ jの型
* @param i 上書きする変数
* @param j 比較する変数
* @return bool 置き換えたかどうか
*/
template <typename T1_, typename T2_>
inline bool chmin(T1_ &i, const T2_ j) noexcept(except) {
if (i > j) {
i = j;
return true;
}
return false;
}
/**
* @brief 配列内の全要素を出力します
*
* @tparam T 配列の型(vector<T>)
* @param v 配列
* @param s 区切り文字(規定ではスペース)
* @author https://zenn.dev/antyuntyun
*/
template <typename T>
inline void print(const vector<T> &v, const string &s = " ") noexcept(except) {
rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");
}
template <typename A, typename B>
inline void print(const vector<pair<A, B>> &v, const string &s = "\n") noexcept(except) {
rep(i, v.size()) cout << v[i].first << " " << v[i].second << s;
}
/// @brief 二次元配列の全要素を出力します
/// @tparam T 配列の型(vector<vector<T>>)
/// @param v 二次元配列
/// @param s 区切り文字
template <typename T>
inline void print(const vector<vector<T>> &v, string const &s = " ") noexcept(except) {
rep(i, v.size()) {
rep(j, v[i].size()) cout << v[i][j] << (j != (ll)v[i].size() - 1 ? s : "\n");
}
}
template <typename T>
inline istream &operator>>(istream &os, vector<T> &v) {
assert(v.size() != 0);
rep(i, v.size()) {
cin >> v[i];
}
return os;
}
/**
* @brief 文字列を反転した文字列を返します
*
* @param s 反転する文字列
* @return string 反転後の文字列
*/
inline string srev(string s) noexcept(except) {
reverse(all(s));
return s;
}
/// @brief long longでべき乗します
/// @param x x^nのx
/// @param n x^nのn
/// @return x^n
inline unsigned long long pow_ll(unsigned long long x, unsigned long long n) noexcept(except) {
ull ret = 1LL;
while (n > 0) {
if (n & 1LL)
ret *= x;
x *= x;
n >>= 1LL;
}
return ret;
}
template <typename T>
inline vector<vector<T>> make_vec2(const ull H, const ull W, const T &init) {
return vector<vector<T>>(H, vector<T>(W, init));
}
template <typename T>
inline vector<vector<T>> make_vec2(const ull H, const ull W) {
return vector<vector<T>>(H, vector<T>(W));
}
template <typename T>
inline vector<vector<vector<T>>> make_vec3(const ull X, const ull Y, const ull Z, const T &init) {
return vector<vector<vector<T>>>(X, make_vec2<T>(Y, Z, init));
}
template <typename T>
inline vector<vector<vector<T>>> make_vec3(const ull X, const ull Y, const ull Z) {
return vector<vector<vector<T>>>(X, make_vec2<T>(Y, Z));
}
/// @brief N進数の文字から10進数の数値に変換します
/// @param c N進数の文字
/// @return 変換した10進数の数値
inline int ntodec(const char c) {
switch (c) {
case '0':
return 0;
case '1':
return 1;
case '2':
return 2;
case '3':
return 3;
case '4':
return 4;
case '5':
return 5;
case '6':
return 6;
case '7':
return 7;
case '8':
return 8;
case '9':
return 9;
case 'A':
return 10;
case 'B':
return 11;
case 'C':
return 12;
case 'D':
return 13;
case 'E':
return 14;
case 'F':
return 15;
case 'G':
return 16;
case 'H':
return 17;
case 'I':
return 18;
case 'J':
return 19;
case 'K':
return 20;
case 'L':
return 21;
case 'M':
return 22;
case 'N':
return 23;
case 'O':
return 24;
case 'P':
return 25;
case 'Q':
return 26;
case 'R':
return 27;
case 'S':
return 28;
case 'T':
return 29;
case 'U':
return 30;
case 'V':
return 31;
case 'W':
return 32;
case 'X':
return 33;
case 'Y':
return 34;
case 'Z':
return 35;
default:
return -1;
}
}
/// @brief 10進数の数値をN進数の文字に変換します
/// @param n 10進数の数値
/// @return N進数の文字
inline char decton(const int n) {
switch (n) {
case 0:
return '0';
case 1:
return '1';
case 2:
return '2';
case 3:
return '3';
case 4:
return '4';
case 5:
return '5';
case 6:
return '6';
case 7:
return '7';
case 8:
return '8';
case 9:
return '9';
case 10:
return 'A';
case 11:
return 'B';
case 12:
return 'C';
case 13:
return 'D';
case 14:
return 'E';
case 15:
return 'F';
case 16:
return 'G';
case 17:
return 'H';
case 18:
return 'I';
case 19:
return 'J';
case 20:
return 'K';
case 21:
return 'L';
case 22:
return 'M';
case 23:
return 'N';
case 24:
return 'O';
case 25:
return 'P';
case 26:
return 'Q';
case 27:
return 'R';
case 28:
return 'S';
case 29:
return 'T';
case 30:
return 'U';
case 31:
return 'V';
case 32:
return 'W';
case 33:
return 'X';
case 34:
return 'W';
case 35:
return 'Z';
default:
return '\0';
}
}
/// @brief N進数の文字列をM進数に直して出力します。
/// @param str N進数の文字
/// @param n 文字の進数
/// @param m 出力の進数
/// @return M進数の文字
inline string n_ary(const string &str, const int n, const int m) {
unsigned long tmp = 0;
string ret;
for (unsigned long long i = 0; i < str.length(); i++) {
tmp += (unsigned long)ntodec(str[str.length() - 1 - i]) * pow_ll(n, i);
}
if (tmp == 0)
return "0";
while (tmp != 0) {
ret = decton(tmp % m) + ret;
tmp /= m;
}
return ret;
}
/// @brief
/// @tparam T nの型
/// @param n 素因数分解する数
/// @return 不明
template <typename T>
inline map<T, T> prime_factor_map(T n) {
map<T, T> ret;
for (T i = 2; i * i <= n; i++) {
T tmp = 0;
while (n % i == 0) {
tmp++;
n /= i;
}
ret[i] = tmp;
}
if (n != 1)
ret[n] = 1;
return ret;
}
// O(sqrt(N))
vector<pair<long long, long long>> prime_factor(long long N) {
// 答えを表す可変長配列
vector<pair<long long, long long>> res;
// √N まで試し割っていく
for (long long p = 2; p * p <= N; ++p) {
// N が p で割り切れないならばスキップ
if (N % p != 0) {
continue;
}
// N の素因数 p に対する指数を求める
int e = 0;
while (N % p == 0) {
// 指数を 1 増やす
++e;
// N を p で割る
N /= p;
}
// 答えに追加
res.emplace_back(p, e);
}
// 素数が最後に残ることがありうる
if (N != 1) {
res.emplace_back(N, 1);
}
return res;
}
/// @brief Nの約数の数を求めます
/// @tparam T Nの型
/// @param N 約数の数を求める数
/// @return Nの約数の数
template <typename T>
inline T divisor_num(const T N) {
map<T, T> pf = __prime_factor(N);
T ret = 1;
for (auto p : pf) {
ret *= (p.second + 1);
}
return ret;
}
/// @brief nの約数を全列挙します。(計算量: O(sqrt(N)))
/// @param n 全列挙する約数
/// @return nの約数
inline vll divisor(const ll n) {
vll ret;
for (ll i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n)
ret.push_back(n / i);
}
}
sort(ret.begin(), ret.end());
return ret;
}
/// @brief 文字列が数字のみか判定します O(|S|)
/// @param s 判定する文字列
/// @return 数値でできた文字列かどうか
inline bool isint(const string &s) noexcept(except) {
rep(i, s.size()) {
if (!isdigit(s[i])) {
return false;
}
}
return true;
}
/// @brief 二次元配列を90度時計回りに回転する
/// @tparam T 配列の型(vector<vector<T>>)
/// @param arr 二次元配列
/// @return 返り値
template <typename T>
inline vector<vector<T>> rot90(const vector<vector<T>> &A) {
ll N = A.size(), M = A[0].size();
vector<vector<T>> ret(M, vector<T>(N));
ll _i = 0, _j = 0;
rep(j, M) {
for (ll i = N - 1; i >= 0; i--) {
ret[_i][_j] = A[i][j];
_j++;
}
_j = 0;
_i++;
}
return ret;
}
/// @brief 回文かどうか判定
/// @param str 文字列
/// @return 回文かどうか
inline bool ispalind(const string &str) noexcept(except) {
ull n = str.length();
for (ull i = 0; i < n / 2; i++) {
if (str[i] != str[n - i - 1]) {
return false;
}
}
return true;
}
inline bool ispalind(const string &str, ull x, ull n) {
assert(x < str.size());
assert(x + n <= str.size());
for (ull i = 0; i < n / 2; i++) {
if (str[x + i] != str[(x + n) - i - 1]) {
return false;
}
}
return true;
}
/// @brief startからnまでの順列を生成
/// @param n 最大値
/// @param start 開始値
/// @return startからnまでの順列
inline vector<ll> range(const ll n, const ll start = 0) {
vector<ll> ret(n - start);
ll oi = 0;
for (ll i = start; i <= n; i++) {
ret[oi] = i;
oi++;
}
return ret;
}
/// @brief 10進法で表した時の各桁の和を求めます
/// @param s 10進法で表した文字列
/// @return 各桁の和
inline ll csum(const string &s) noexcept(except) {
ll ret = 0;
rep(i, s.size()) {
ret += ctoi(s[i]);
}
return ret;
}
/// @brief csumの数値用の補完関数
/// @param n 数値
/// @return 各桁の和
inline ll csum(const ll n) noexcept(except) {
return csum(to_string(n));
}
/// @brief 階乗を計算する
/// @param n nの階乗
/// @return nの階乗
inline ll fact(const ll n) noexcept(except) {
ll ret = 1;
rep(i, n) {
ret *= i + 1;
}
return ret;
}
/// @brief 平方数かどうかを判定
/// @param N 判定する数
/// @return 平方数かどうか
inline bool is_squere(const ll N) noexcept(except) {
long long r = (long long)floor(sqrt((long double)N)); // 切り捨てした平方根
return (r * r) == N;
}
/// @brief 一次元の累積和を返します
/// @tparam T vectorの型
/// @param v 加工する前の配列
/// @return 加工後の配列(長さは |v|+1 となります。)
template <typename T>
inline vector<T> cum(const vector<T> &v) noexcept(except) {
vector<T> ans(v.size() + 1);
ans[0] = 0;
for (ull i = 1; i <= v.size(); i++) {
ans[i] = ans[i - 1] + v[i - 1];
}
return ans;
}
/// @brief 二次元の累積和を返します
/// @tparam T vector<vector<>>の型
/// @param v 加工前の配列
/// @return 加工後の配列(長さはそれぞれ+1になります)
template <typename T>
inline vec2<T> cum(const vec2<T> &v) {
assert(v.size() > 0);
ull H = v.size(), W = v[0].size();
auto ret = make_vec2<T>(H + 1, W + 1, 0);
for (ull i = 1; i <= H; i++) {
for (ull j = 1; j <= W; j++) {
ret[i][j] = ret[i][j - 1] + v[i - 1][j - 1];
}
}
for (ull j = 1; j <= W; j++) {
for (ull i = 1; i <= H; i++) {
ret[i][j] += ret[i - 1][j];
}
}
return ret;
}
template <typename T>
inline vec3<T> cum(const vec3<T> &v) {
assert(v.size() > 0 && v[0].size() > 0);
ll x = v.size();
ll y = v[0].size();
ll z = v[0][0].size();
auto ret = make_vec3<T>(x + 1, y + 1, z + 1, 0);
for (ll i = 0; i < x; ++i) {
for (ll j = 0; j < y; ++j) {
for (ll k = 0; k < z; ++k) {
ret[i + 1][j + 1][k + 1] =
ret[i][j + 1][k + 1] + ret[i + 1][j][k + 1] +
ret[i + 1][j + 1][k] - ret[i][j][k + 1] - ret[i][j + 1][k] -
ret[i + 1][j][k] + ret[i][j][k] + v[i][j][k];
}
}
}
return ret;
}
template <typename T>
inline ll cumcnt(const vec2<T> &z, ll lx, ll ly, ll rx, ll ry) {
return z[rx][ry] + z[lx - 1][ly - 1] - z[lx - 1][ry] - z[rx][ly - 1];
}
template <typename T>
inline ll cumcnt(const vec3<T> &z, ll lx, ll ly, ll lz, ll rx, ll ry, ll rz) {
return z[rx][ry][rz] - z[lx - 1][ry][rz] - z[rx][ly - 1][rz] - z[rx][ry][lz - 1] + z[lx - 1][ly - 1][rz] + z[lx - 1][ry][lz - 1] + z[rx][ly - 1][lz - 1] - z[lx - 1][ly - 1][lz - 1];
}
#ifdef cpp20
template <integral T>
#else
template <typename T>
#endif
inline vector<T> cumxor(const vector<T> &x) {
vector<T> ans(x.size() + 1);
ans[0] = 0;
irep(i, x.size()) {
ans[i] = ans[i - 1] ^ x[i - 1];
}
return ans;
}
/// @brief ランダムな数値を返す
/// @param l 最小値
/// @param r 最大値
/// @return
inline ll randint(const ll l, const ll r) noexcept(except) {
if (l == r)
return l;
return l + (rand() % (r - l));
}
/// @brief ランダムな小数を返す(0<=x<=1)
/// @return 0<=x<=1
inline ld randd() noexcept(except) {
return 1.0L * rand() / RAND_MAX;
}
/// @brief 高速全探索 O(log N)
/// @tparam T 配列の型
/// @param v 配列
/// @param x 探索するやつ
/// @return 数
template <typename T>
inline long long bound_count(const vector<T> &v, const T &x) noexcept(except) {
auto l = lower_bound(v.begin(), v.end(), x);
auto u = upper_bound(v.begin(), v.end(), x);
if (*l != x) {
return 0;
}
if (u == v.end()) {
return v.size() - (l - v.begin());
} else {
return (u - v.begin()) - (l - v.begin());
}
}
/// @brief 配列の最近値を求める
/// @tparam T 配列の型
/// @param v 配列
/// @param x 最近値を求める値
/// @return xの最近値
template <typename T>
inline T recent(const vector<T> &v, const T &x) {
auto it = lower_bound(all(v), x);
if (it == v.end())
return *prev(v.end(), 1);
else {
if (it == v.begin())
return *v.begin();
else {
if (abs(*it - x) < abs(*prev(it, 1) - x))
return *it;
else
return *prev(it, 1);
}
}
}
/// @brief 文字列圧縮
/// @param str 圧縮する文字列
/// @return 圧縮後
inline vector<pair<char, ull>> rlencode(const string &str) noexcept(except) {
ull n = (ull)str.size();
vector<pair<char, ull>> ret;
for (ull l = 0; l < n;) {
ull r = l + 1;
for (; r < n && str[l] == str[r]; r++) {
};
ret.push_back({str[l], r - l});
l = r;
}
return ret;
}
template <typename T>
inline map<T, ll> counter(const vector<T> &v) noexcept(except) {
map<T, ll> dat;
rep(i, v.size()) {
dat[v[i]]++;
}
return dat;
}
inline map<char, ll> counter(const string &s) noexcept(except) {
map<char, ll> dat;
rep(i, s.size()) {
dat[s[i]]++;
}
return dat;
}
/// @brief ユークリッド距離
/// @param x1
/// @param y1
/// @param x2
/// @param y2
/// @return
inline ld euclidean(const ld x1, const ld y1, const ld x2, const ld y2) noexcept(except) {
ld dx = x2 - x1;
ld dy = y2 - y1;
ld distance = sqrt(dx * dx + dy * dy);
return distance;
}
/// @brief 配列の範囲(閉区間)に属する値の個数を計算
/// @tparam T 配列の値型
/// @param v 配列
/// @param l 左端
/// @param r 右端
/// @return
template <typename T>
inline ll lencnt(const vector<T> &v, const T &l, const T &r) {
return upper_bound(all(v), r) - lower_bound(all(v), l);
}
using GraphKey = ll;
struct CostEdge {
GraphKey to;
ll cost;
#if __cplusplus >= 202002L
auto operator<=>(const CostEdge &e) const {
return this->cost <=> e.cost;
}
#endif
bool operator==(const CostEdge &e) const {
return this->cost == e.cost;
}
};
struct FromCostEdge : CostEdge {
GraphKey from;
};
ostream &operator<<(ostream &os, const CostEdge &cost) {
os << "{ to: " << cost.to << ", cost: " << cost.cost << " }";
return os;
}
using Edge = GraphKey;
using Graph = vector<vector<Edge>>;
using CostGraph = vector<vector<CostEdge>>;
inline CostEdge make_cost(const GraphKey to, const ll cost) noexcept {
return CostEdge{to, cost};
}
inline CostGraph to_costgraph(const Graph &g) noexcept {
CostGraph ans(g.size());
rep(i, g.size()) {
rep(j, g[i].size()) {
ans[i].emplace_back(CostEdge{g[i][j], 1});
}
}
return ans;
}
inline pair<GraphKey, ll> __tree_diamiter_dfs(const CostGraph &G, ll u, ll par) { // 最遠点間距離と最遠点を求める
pair<GraphKey, ll> ret = make_pair((GraphKey)0, u);
for (auto e : G[u]) {
if (e.to == par)
continue;
auto next = __tree_diamiter_dfs(G, e.to, u);
next.first += e.cost;
ret = max(ret, next);
}
return ret;
}
// 木の直径
inline GraphKey tree_diamiter(const CostGraph &G) {
pair<GraphKey, ll> p = __tree_diamiter_dfs(G, 0LL, -1LL);
pair<GraphKey, ll> q = __tree_diamiter_dfs(G, p.second, -1LL);
return q.first;
}
// 木の直径
inline GraphKey tree_diamiter(const Graph &G) {
return tree_diamiter(to_costgraph(G));
}
inline vector<ll> dijkstra(const CostGraph &G, ll start = 0, ll init = 0) {
ll n = G.size();
assert(0 <= start && start < n);
vector<bool> kakutei(n, false);
vll cur(n, INFLL);
reverse_queue<pll> q;
cur[start] = init;
q.push(make_pair(cur[start], start));
while (!q.empty()) {
ll pos = q.top().second;
q.pop();
if (kakutei[pos])
continue;
kakutei[pos] = true;
rep(i, G[pos].size()) {
ll nex = G[pos][i].to;
ll cost = G[pos][i].cost;
if (cur[nex] > cur[pos] + cost) {
cur[nex] = cur[pos] + cost;
q.push(make_pair(cur[nex], nex));
}
}
}
return cur;
}
inline vector<ll> dijkstra(const CostGraph &G, vll &prv, ll start = 0, ll init = 0) {
ll n = G.size();
assert(0 <= start && start < n);
vector<bool> kakutei(n, false);
vll cur(n, INFLL);
prv.resize(G.size(), -1);
reverse_queue<pll> q;
cur[start] = init;
q.push(make_pair(cur[start], start));
while (!q.empty()) {
ll pos = q.top().second;
q.pop();
if (kakutei[pos])
continue;
kakutei[pos] = true;
rep(i, G[pos].size()) {
ll nex = G[pos][i].to;
ll cost = G[pos][i].cost;
if (cur[nex] > cur[pos] + cost) {
cur[nex] = cur[pos] + cost;
prv[nex] = pos;
q.push(make_pair(cur[nex], nex));
}
}
}
return cur;
}
inline vector<ll> get_path(const vector<ll> &prev, ll t) {
vector<ll> path;
for (ll cur = t; cur != -1; cur = prev[cur]) {
path.push_back(cur);
}
reverse(path.begin(), path.end()); // 逆順なのでひっくり返す
return path;
}
inline vector<ll> dijkstra(const Graph &G, ll start = 0, ll init = 0) {
return dijkstra(to_costgraph(G), start, init);
}
inline vector<ll> dijkstra(const Graph &G, vll &prv, ll start = 0, ll init = 0) {
return dijkstra(to_costgraph(G), prv, start, init);
}
inline vector<vector<ll>> warshall_floyd(const CostGraph &G) {
ll n = G.size();
vvll d = make_vec2<ll>(n, n, INFLL);
rep(i, n) {
d[i][i] = 0;
}
rep(i, n) {
rep(j, G[i].size()) {
d[i][G[i][j].to] = G[i][j].cost;
}
}
rep(k, n) {
rep(i, n) {
rep(j, n) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
return d;
}
inline vector<vector<ll>> warshall_floyd(const Graph &G) {
return warshall_floyd(to_costgraph(G));
}
template <ull bit, ull n>
class CustomBit {
public:
explicit CustomBit(ull val = 0) {
this->__val = val;
this->__max_val = pow_ll(bit, n) - 1;
this->__reload();
}
ull to_ull() const {
return this->__val;
}
// O(1)
ull max_val() const {
return this->__max_val;
}
// O(1)
array<ull, n> get_all() const {
return this->__dat;
}
// O(1)
ull get(ull x) const {
assert(x < n);
return this->__dat[x];
}
// O(1)
constexpr ull size() const {
return n;
}
constexpr void set(ull x, ull val) {
assert(val < bit);
this->__dat[x] = val;
this->__reload_val();
}
CustomBit &operator++(int) {
this->__val++;
this->__reload();
return *this;
}
CustomBit &operator++() {
auto tmp = *this;
++this->__val;
this->__reload();
return tmp;
}
private:
ull __val;
array<ull, n> __dat;
ull __max_val;
void __reload() {
assert(0 <= this->__val && this->__val <= this->__max_val);
auto tmp = this->__val;
for (ll i = 0; i < n; ++i) {
this->__dat[i] = tmp % bit;
tmp /= bit;
}
}
void __reload_val() {
this->__val = 0;
ull a = 1;
for (ll i = 0; i < n; ++i) {
this->__val += a * this->__dat[i];
a *= bit;
}
}
};
template <ull bit, ull n>
ostream &operator<<(ostream &os, const CustomBit<bit, n> &bits) {
os << "[";
for (ll i = 0; i < n; ++i) {
os << bits.get(i) << (i != n - 1 ? ", " : "");
}
os << "](bit: " << bit << ")";
return os;
}
/// @brief Union-Find 木
/// @note 1.4 高速化 + 省メモリ化
/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find
class UnionFind {
public:
UnionFind() = default;
/// @brief Union-Find 木を構築します。
/// @param n 要素数
explicit UnionFind(size_t n)
: m_parentsOrSize(n, -1) {}
/// @brief 頂点 i の root のインデックスを返します。
/// @param i 調べる頂点のインデックス
/// @return 頂点 i の root のインデックス
ll find(ll i) {
if (m_parentsOrSize[i] < 0) {
return i;
}
// 経路圧縮
return (m_parentsOrSize[i] = find(m_parentsOrSize[i]));
}
/// @brief a のグループと b のグループを統合します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
void merge(ll a, ll b) {
a = find(a);
b = find(b);
if (a != b) {
// union by size (小さいほうが子になる）
if (-m_parentsOrSize[a] < -m_parentsOrSize[b]) {
std::swap(a, b);
}
m_parentsOrSize[a] += m_parentsOrSize[b];
m_parentsOrSize[b] = a;
}
}
/// @brief a と b が同じグループに属すかを返します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
/// @return a と b が同じグループに属す場合 true, それ以外の場合は false
bool connected(ll a, ll b) {
return (find(a) == find(b));
}
/// @brief i が属するグループの要素数を返します。
/// @param i インデックス
/// @return i が属するグループの要素数
ll size(ll i) {
return -m_parentsOrSize[find(i)];
}
private:
// m_parentsOrSize[i] は i の 親,
// ただし root の場合は (-1 * そのグループに属する要素数)
std::vector<ll> m_parentsOrSize;
};
inline vector<FromCostEdge> to_fromcostedges(const CostGraph &g) {
vector<FromCostEdge> dat;
rep(i, g.size()) {
rep(j, g[i].size()) {
dat.emplace_back(FromCostEdge{{g[i][j].to, g[i][j].cost}, i});
}
}
return dat;
}
/// @brief 最小・最大全域木
/// @param e 辺(ソート済み)
/// @param v 頂点数
/// @return
/// @see https://x.gd/7JLRg
inline ll get_mst(const vector<FromCostEdge> &edges, ll v) {
UnionFind uf(v);
ll sum = 0;
for (const auto &edge : edges) {
if (!uf.connected(edge.from, edge.to)) {
uf.merge(edge.from, edge.to);
sum += edge.cost;
}
}
return sum;
}
#ifdef cpp20
template <number T>
#else
template <typename T>
#endif
inline T sum(const vector<T> &v) {
T ans = 0;
rep(i, v.size()) ans += v[i];
return ans;
}
#ifdef cpp20
template <number T>
#else
template <typename T>
#endif
inline vector<T> zaatsu(const vector<T> &A) {
vector<T> B = A;
// B を小さい順にソート
sort(B.begin(), B.end());
// B から重複を除去する
B.erase(unique(B.begin(), B.end()), B.end());
// 座標圧縮した結果を求める
vector<T> res(A.size());
for (ull i = 0; i < A.size(); ++i) {
res[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
}
return res;
}
#ifdef cpp20
// https://x.gd/yonBS
class Doubling {
public:
explicit Doubling(const vll &x, ull max_k) {
k = bit_width(max_k);
n = x.size();
dp = make_vec2<ll>(k + 1, n);
this->max_k = max_k;
rep(j, n) dp[0][j] = x[j];
irep(i, k) {
rep(j, n) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
}
ull to(ull pos, ull k) const {
assert(k <= max_k);
ll now = pos;
for (ull i = 0; k > 0; ++i) {
if (k & 1) now = dp[i][now];
k >>= 1;
}
return now;
}
private:
ull n;
ull k;
ull max_k;
vvll dp;
};
#endif
/* #endregion */
/* Variables */
ll N, M, K, Q;
ll H, W;
string S = "";
string dump = "";
ll codeforces_t = -1;
/* Main Function */
using mint = modint998244353;
mint was(ll n) {
auto mn = mint(n);
return (mn * (mn + 1) * (2 * mn + 1)) / mint(6);
}
int main() {
fastio;
cin >> M >> N;
if (N == 0) {
co(was(M).val());
exit;
}
vll X(N);
cin >> X;
mint ans = 0;
ll prvm = 0;
rep(i, N) {
ans += was(X[i] - prvm - 1);
debug(i, X[i] - prvm - 1, ans);
prvm = X[i];
}
ans += was(M - prvm);
co(ans.val());
return 0;
}
/* 文字化け注意 */