#873845 (C++17) No.2324 Two Countries within UEC

提出ソース
結果

問題	No.2324 Two Countries within UEC
ユーザー	🦠みどりむし
提出日時	2023-05-28 13:45:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	67 ms / 2,000 ms
コード長	61,861 bytes
コンパイル時間	2,223 ms
コンパイル使用メモリ	215,428 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-26 23:16:03
合計ジャッジ時間	5,186 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	61 ms 6,812 KB
testcase_01	AC	65 ms 6,940 KB
testcase_02	AC	13 ms 6,944 KB
testcase_03	AC	49 ms 6,940 KB
testcase_04	AC	56 ms 6,940 KB
testcase_05	AC	14 ms 6,940 KB
testcase_06	AC	24 ms 6,940 KB
testcase_07	AC	12 ms 6,940 KB
testcase_08	AC	48 ms 6,940 KB
testcase_09	AC	49 ms 6,944 KB
testcase_10	AC	67 ms 6,944 KB
testcase_11	AC	62 ms 6,944 KB
testcase_12	AC	21 ms 6,940 KB
testcase_13	AC	21 ms 6,944 KB
testcase_14	AC	13 ms 6,944 KB
testcase_15	AC	12 ms 6,944 KB
testcase_16	AC	45 ms 6,940 KB
testcase_17	AC	29 ms 6,944 KB
testcase_18	AC	14 ms 6,940 KB
testcase_19	AC	66 ms 6,940 KB
testcase_20	AC	10 ms 6,940 KB
testcase_21	AC	33 ms 6,944 KB
testcase_22	AC	43 ms 6,940 KB
testcase_23	AC	15 ms 6,944 KB
testcase_24	AC	36 ms 6,944 KB
testcase_25	AC	66 ms 6,940 KB
testcase_26	AC	28 ms 6,944 KB
testcase_27	AC	31 ms 6,940 KB
testcase_28	AC	28 ms 6,940 KB
testcase_29	AC	27 ms 6,944 KB
testcase_30	AC	28 ms 6,940 KB
testcase_31	AC	2 ms 6,944 KB
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	2 ms 6,944 KB
testcase_34	AC	1 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	2 ms 6,944 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	1 ms 6,944 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	2 ms 6,940 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ GCC */
/* #region template */
#include <bits/stdc++.h>

/* #expanded [template.hpp] */
/* #expanded [snippet/aliases.hpp] */
#include <cstdint>
#include <utility>
#include <vector>
/* #expanded [internal/dev_env.hpp] */
#ifdef LOCAL_JUDGE
constexpr bool DEV_ENV = true;constexpr bool NO_EXCEPT = false;
#else
constexpr bool DEV_ENV = false;constexpr bool NO_EXCEPT = true;
#endif
/* [internal/dev_env.hpp] */
/* #expanded [snippet/internal/types.hpp] */
#include <cstdint>
namespace lib {using i16 = std::int16_t;using u16 = std::uint16_t;using i32 = std::int32_t;using u32 = std::uint32_t;using i64 = std::int64_t;using u64 = std::uint64_t;
#ifdef __GNUC__
using i128 = __int128_t;using u128 = __uint128_t;
#endif
using uint = unsigned;using ll = long long;using ull = unsigned long long;using ld = long double;}
/* [snippet/internal/types.hpp] */
#define until(...) while(!(__VA_ARGS__))
#define ALL(x) std::begin((x)),std::end((x))
#define RALL(x) std::rbegin((x)),std::rend((x))
#define $F first
#define $S second
namespace lib {template<class T> using spair = std::pair<T,T>;}namespace std {using bit_reference = std::vector<bool>::reference;bit_reference operator |= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a | b; }bit_reference operator &= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a & b; }}
/* [snippet/aliases.hpp] */
/* #expanded [snippet/iterations.hpp] */
/* #expanded [snippet/internal/overload.hpp] */
#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
/* [snippet/internal/overload.hpp] */
#define LOOP(n) REPI($_, (n))
#define REPI(i,n) for(int i=0, i##_length=(n); i<i##_length; ++i)
#define REPF(i,l,r) for(auto i=(l), i##_last=(r); i<i##_last; ++i)
#define REPIS(i,l,r,s) for(auto i=(l), i##_last=(r); i<i##_last; i+=(s))
#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(auto i=(r), i##_last=(l); --i>=i##_last;)
#define REPRS(i,l,r,s) for(auto i=(r), i##_last=(l); (i-=(s))>=i##_last;)
#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)
#define FORO(i,n) for(int i=0, i##_last=(n); i<=i##_last; ++i)
#define FORI(i,l,r) for(auto i=(l), i##_last=(r); i<=i##_last; ++i)
#define FORIS(i,l,r,s) for(auto i=(l), i##_last=(r); i<=i##_last; i+=(s))
#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(auto i=(r), i##_last=(l); i>=i##_last; --i)
#define FORRS(i,l,r,s) for(auto i=(r), i##_last=(l); i>=i##_last; i-=(s))
#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)
#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))
#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))
#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))
#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))
#define ITR(...) $OVERLOAD5(__VA_ARGS__, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD5(__VA_ARGS__, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD5(__VA_ARGS__, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
/* [snippet/iterations.hpp] */
/* #expanded [snippet/fast_io.hpp] */
#include <iostream>
#ifdef __GNUC__
__attribute__((constructor)) inline void fast_io() noexcept(NO_EXCEPT) { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); }
#else
inline void fast_io() noexcept(NO_EXCEPT) { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); }
#endif
/* [snippet/fast_io.hpp] */
/* #expanded [snippet/using.hpp] */
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <stack>
/* #expanded [utilities.hpp] */
/* #expanded [numeric/int128.hpp] */
#include <cctype>
#include <cassert>
#include <iostream>
#include <string>
#include <algorithm>
template<class C, class S>std::basic_istream<C,S>& operator>>(std::basic_istream<C,S>& in, lib::i128& v) noexcept(NO_EXCEPT) {std::string str; in >> str;v = 0;bool negative = (str[0] == '-');REP(d, std::next(str.begin(), negative), str.end()) {assert(std::isdigit(*d));v = v * 10 + *d - '0';}if(negative) v *= -1;return in;}template<class C, class S>std::basic_ostream<C,S>& operator<<(std::basic_ostream<C,S>& out, lib::i128 v) noexcept(NO_EXCEPT) {if(v == 0) return out << 0;if(v < 0) out << '-', v *= -1;std::string str;while(v > 0) str += v%10 + '0', v /= 10;std::reverse(str.begin(), str.end());return out << str;}
/* [numeric/int128.hpp] */
/* #expanded [geometry.hpp] */
/* #expanded [geometry/basic.hpp] */
/* #expanded [geometry/point.hpp] */
#include <complex>
#include <cmath>
#include <iostream>
#include <utility>
namespace lib {template <class T> struct point : protected std::pair<T,T> {public:constexpr point() {}constexpr point(const T& x, const T& y) noexcept(NO_EXCEPT) : std::pair<T,T>(x, y) {}template<class U> constexpr point(const point<U>& p) noexcept(NO_EXCEPT) : point(p.x(), p.y()) {};template<class U> constexpr point(point<U>&& p) noexcept(NO_EXCEPT) : point(p.x(), p.y()) {};template<class U>constexpr point& operator=(const point<U>& p) & noexcept(NO_EXCEPT) { this->x() = p.x(),this->y() = p.y(); return *this; };template<class U>constexpr point& operator=(point<U>&& p) && noexcept(NO_EXCEPT) { this->x() = p.x(), this->y() = p.y(); return *this; };inline T& x() noexcept(NO_EXCEPT) { return this->first; }inline T& y() noexcept(NO_EXCEPT) { return this->second; }inline const T& x() const noexcept(NO_EXCEPT) { return this->first; }inline const T& y() const noexcept(NO_EXCEPT) { return this->second; }inline constexpr point& operator+=(const point& v) noexcept(NO_EXCEPT) { this->x() += v.x(), this->y() += v.y(); return *this; }inline constexpr point& operator-=(const point& v) noexcept(NO_EXCEPT) { this->x() -= v.x(), this->y() -= v.y(); return *this; }friend inline constexpr point operator+(point a, const point& b) noexcept(NO_EXCEPT) { return a += b; }friend inline constexpr point operator-(point a, const point& b) noexcept(NO_EXCEPT) { return a -= b; }friend inline constexpr point operator*(const point& a, const point& b) noexcept(NO_EXCEPT) { return a.x() * b.x() + a.y() * b.y(); }friend inline constexpr bool operator==(const point& a, const point& b) noexcept(NO_EXCEPT) { return a.x() == b.x() && a.y() == b.y(); }friend inline constexpr bool operator!=(const point& a, const point& b) noexcept(NO_EXCEPT) { return a.x() != b.x() or a.y() != b.y(); }friend inline constexpr bool operator<(const point& a, const point& b) noexcept(NO_EXCEPT) { return a.x() != b.x() ? a.x() < b.x() : a.y() < b.y(); }friend inline constexpr bool operator>(const point& a, const point& b) noexcept(NO_EXCEPT) { return a.x() != b.x() ? a.x() > b.x() : a.y() > b.y(); }friend inline constexpr bool operator<=(const point& a, const point& b) noexcept(NO_EXCEPT) { return !(a > b); }friend inline constexpr bool operator>=(const point& a, const point& b) noexcept(NO_EXCEPT) { return !(a < b); }std::pair<T,T> _debug() const noexcept(NO_EXCEPT) { return { this->x(), this->y() }; }};}template<class T>inline constexpr T std::abs(const lib::point<T>& v) {T x = v.x(), y = v.y(), n = std::max(std::abs(x), std::abs(y));if(n == 0) return 0;x /= n, y /= n;return n * std::sqrt(x * x + y * y);}namespace lib {template<class U, class T>inline constexpr U distance(const point<T>& a, const point<T>& b) {return std::abs(point<U>(a - b));}template<class T>inline constexpr T cross(point<T> a, point<T> b, const point<T>& o = {}) {a -= o, b -= o;return a.x() * b.y() - a.y() * b.x();}}template<class T, class C, class S>std::basic_istream<C,S>& operator>>(std::basic_istream<C,S>& in, lib::point<T>& v) {T x, y; in >> x >> y;v = { x, y };return in;}
/* [geometry/point.hpp] */
/* [geometry/basic.hpp] */
/* [geometry.hpp] */
/* #expanded [numeric/arithmetic.hpp] */
#include <cassert>
#include <cstring>
#include <string>
#include <algorithm>
#include <atcoder/math.hpp>
/* #expanded [internal/types.hpp] */
#include <cstdint>
namespace lib {namespace internal {using size_t = std::int32_t;using int128_t = __int128_t;using uint128_t = __uint128_t;}}
/* [internal/types.hpp] */
/* #expanded [numeric/internal/number_base.hpp] */
#include <cassert>
#include <cstddef>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
namespace lib {template<std::size_t B = 2, class T>std::string base_n_string(T v) noexcept(NO_EXCEPT) {constexpr char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";static_assert(0 < B and B <= std::strlen(CHARS));assert(0 <= v);std::string res;while(v > 0) {res += CHARS[v%B];v /= B;}std::reverse(ALL(res));return res;}template<class T>std::string base_n_string(T v, std::size_t b) noexcept(NO_EXCEPT) {constexpr char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";assert(1 < b && b <= std::strlen(CHARS));assert(0 <= v);std::string res;while(v > 0) {res += CHARS[v%b];v /= b;}std::reverse(ALL(res));return res;}template<class T>std::vector<T> base_n_vector(T v, std::size_t b = 2) noexcept(NO_EXCEPT) {assert(1 < b);assert(0 <= v);std::vector<T> res;while(v > 0) {res.push_back(v%b);v /= b;}std::reverse(ALL(res));return res;}}
/* [numeric/internal/number_base.hpp] */
namespace lib {template<class T>T sqrt_floor(const T x) noexcept(NO_EXCEPT) {T ok = 0, ng = x / 2 + 2;while(ng - ok > 1) {T mid = (ok + ng) / 2;(x / mid < mid ? ng : ok) = mid;}return ok;}template<class T>T sqrt_ceil(const T x) noexcept(NO_EXCEPT) {T ok = 0, ng = x / 2 + 2;while(ng - ok > 1) {T mid = (ok + ng) / 2;(x <= (mid - 1) * (mid - 1) ? ng : ok) = mid;}return ok;}template<class T>T nPr(const T n, const T r) noexcept(NO_EXCEPT) {assert(0 <= n);assert(0 <= r);if(n < r) return 0;T res = 1;REP(i, r) res *= n-i;return res;}template<class T>T nCr(const T n, const T r) noexcept(NO_EXCEPT) {assert(0 <= n);assert(0 <= r);if(n == r) return 1;if(n < r) return 0;if(n < r*2) r = n-r;T p = 1, q = 1;REP(i, r) p *= n-i, q *= r-i;return p / q;}template<class T, class U>T pow(T x, U n) noexcept(NO_EXCEPT) {T res = 1;while(n > 0) {if(n & 1) res *= x;x *= x;n >>= 1;}return res;}using atcoder::pow_mod;using atcoder::inv_mod;using atcoder::crt;template<class T, class U, class V>inline bool mul_over(const T x, const U y, const V s) noexcept(NO_EXCEPT) {if(x >= s) return true;if(x >= 0 && y >= 0) return x > s/y;if(x <= 0 && y <= 0) return x < s/y;return false;}template<class T, class U, class V>inline bool mul_under(const T x, const U y, const V s) noexcept(NO_EXCEPT) {if(x <= s) return true;if(x >= 0 && y <= 0) return x > s/y;if(x <= 0 && y >= 0) return x < s/y;return false;}}
/* [numeric/arithmetic.hpp] */
/* #expanded [numeric/matrix.hpp] */
#include <cassert>
#include <vector>
/* #expanded [grid.hpp] */
#include <cassert>
#include <iostream>
#include <vector>
#include <string>
#include <type_traits>
#include <iterator>
#include <initializer_list>
#include <utility>
namespace lib {namespace internal {namespace grid_impl {template<class T>struct interface {};template<class T> struct container_base : virtual interface<T> {private:size_t _h, _w;protected:inline void _validate_index(__attribute__ ((unused)) const size_t i, __attribute__ ((unused)) const size_t j) const noexcept(NO_EXCEPT) {assert(0 <= i and i < this->height());assert(0 <= j and j < this->width());}inline size_t _positivize_row_index(const size_t x) const noexcept(NO_EXCEPT) {return x < 0 ? this->height() + x : x;}inline size_t _positivize_col_index(const size_t x) const noexcept(NO_EXCEPT) {return x < 0 ? this->width() + x : x;}public:container_base() noexcept(NO_EXCEPT) = default;container_base(const size_t _h, const size_t _w) noexcept(NO_EXCEPT) : _h(_h), _w(_w) {}virtual void resize(const size_t h, const size_t w) noexcept(NO_EXCEPT) /*override*/ {this->_h = h, this->_w = w;}inline size_t height() const noexcept(NO_EXCEPT) /*override*/ { return this->_h; }inline size_t width() const noexcept(NO_EXCEPT) /*override*/ { return this->_w; }inline size_t id(const size_t i, const size_t j) const noexcept(NO_EXCEPT) /*override*/ {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);this->_validate_index(_i, _j);return _i * this->width() + _j;}};template<class T, class Row = std::vector<T>, class base = std::vector<Row>>struct container : base, container_base<T>, virtual interface<T> {container(const size_t n = 0) noexcept(NO_EXCEPT) : container(n, n) {}container(const size_t h, const size_t w, const T &val = T{}) noexcept(NO_EXCEPT) : base(h, Row(w, val)), container_base<T>(h, w) {}container(const std::initializer_list<Row> init_list) noexcept(NO_EXCEPT) : base(init_list) {const size_t rows = std::distance(ALL(init_list));const size_t first_cols = init_list.begin()->size();if constexpr (DEV_ENV) { ITR(init_row, init_list) assert((size_t)init_row.size() == first_cols); }this->container_base<T>::resize(rows, first_cols);}inline void assign(const container &source) noexcept(NO_EXCEPT) {this->resize(source.height(), source.width());this->base::assign(ALL(source));}inline void assign(const size_t h, const size_t w, const T &val = T{}) noexcept(NO_EXCEPT) /*override*/ {this->container_base<T>::resize(h, w);this->base::resize(h);ITRR(row, *this) row.assign(w, val);}inline void resize(const size_t h, const size_t w) noexcept(NO_EXCEPT) /*override*/ {this->container_base<T>::resize(h, w);this->base::resize(h);ITRR(row, *this) row.resize(w);}inline T& operator()(const size_t i, const size_t j) noexcept(NO_EXCEPT) /*override*/ {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);this->_validate_index(_i, _j);return (*this)[_i][_j];}inline const T& operator()(const size_t i, const size_t j) const noexcept(NO_EXCEPT) /*override*/ {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);this->_validate_index(_i, _j);return (*this)[_i][_j];}};template<class T, class base = std::vector<T>>struct unfolded_container : base, container_base<T>, virtual interface<T> {unfolded_container(size_t n = 0) noexcept(NO_EXCEPT) : unfolded_container(n, n) {}unfolded_container(const size_t h, const size_t w, const T &val = T{}) noexcept(NO_EXCEPT) : base(h*w, val), container_base<T>(h, w) {}unfolded_container(std::initializer_list<std::initializer_list<T>> init_list) noexcept(NO_EXCEPT) {const size_t rows = std::distance(init_list.begin(), init_list.end());const size_t first_cols = init_list.begin()->size();this->resize(rows, first_cols);for(auto index=0, itr=init_list.begin(), itr_end=init_list.end(); itr!=itr_end; ++itr) {assert((size_t)itr->size() == first_cols);for(auto v=itr->begin(), v_end=itr->end(); v!=v_end; ++v) (*this)[index++] = *v;}}inline void assign(const unfolded_container &source) noexcept(NO_EXCEPT) {this->resize(source.height(), source.width());this->base::assign(ALL(source));}inline void assign(const size_t h, const size_t w, const T &val = T{}) noexcept(NO_EXCEPT) /*override*/ {this->container_base<T>::resize(h, w);this->base::assign(h*w, val);}inline void resize(const size_t h, const size_t w) noexcept(NO_EXCEPT) /*override*/ {this->container_base<T>::resize(h, w);this->base::resize(h*w);}inline T& operator()(const size_t i, const size_t j) noexcept(NO_EXCEPT) /*override*/ {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);return (*this)[this->id(_i, _j)];}inline const T& operator()(const size_t i, const size_t j) const noexcept(NO_EXCEPT) /*override*/ {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);return (*this)[this->id(_i, _j)];}};}template<class T, class container> struct grid_core : container, virtual grid_impl::interface<T> {using container::container;enum class invert_direction { vertical, horizontal };enum class rotate_direction { counter_clockwise, clockwise };template<class U = T, class Stream = std::istream>void inline read(Stream *const ist = &std::cin) noexcept(NO_EXCEPT) {REP(i, this->height()) REP(j, this->width()) {U val; *ist >> val;(*this)(i, j) = val;}}template<invert_direction DIRECTION = invert_direction::vertical>inline grid_core& invert() noexcept(NO_EXCEPT) {grid_core res(this->height(), this->width());REP(i, this->height()) REP(j, this->width()) {if constexpr (DIRECTION == invert_direction::vertical) {res(i,j) = (*this)(this->height()-i-1,j);}else {res(i,j) = (*this)(i, this->width()-j-1);}}this->assign(res);return *this;}template<rotate_direction DIRECTION = rotate_direction::clockwise>inline grid_core& rotate(const size_t k) noexcept(NO_EXCEPT) {grid_core res = *this;REP(i, k) { res = res.rotate<DIRECTION>(); }this->assign(res);return *this;}template<rotate_direction DIRECTION = rotate_direction::clockwise>inline grid_core& rotate() noexcept(NO_EXCEPT) {grid_core res(this->width(), this->height());REP(i, this->width()) REP(j, this->height()) {if constexpr (DIRECTION == rotate_direction::clockwise) {res(i,j) = (*this)(this->height()-j-1,i);}else {res(i,j) = (*this)(j,this->width()-i-1);}}this->assign(res);return *this;}inline grid_core& transpose() noexcept(NO_EXCEPT) {grid_core res(this->width(), this->height());REP(i, this->width()) REP(j, this->height()) {res(i,j) = (*this)(j,i);}this->assign(res);return *this;}};}template<class T, class Row = std::vector<T>, class base = std::vector<Row>>using grid = internal::grid_core<T,internal::grid_impl::container<T,Row,base>>;template<class T, class base = std::vector<T>>using unfolded_grid = internal::grid_core<T,internal::grid_impl::unfolded_container<T,base>>;}
/* [grid.hpp] */
/* #expanded [adapter/valarray.hpp] */
#include <cassert>
#include <valarray>
#include <algorithm>
#include <type_traits>
#include <iterator>
#include <initializer_list>
namespace lib {template<class T> struct valarray : std::valarray<T> {using size_type = internal::size_t;using iterator = T*;using const_iterator = const T*;protected:inline bool _validate_index_in_right_open([[maybe_unused]] const size_type p) const noexcept(NO_EXCEPT) {return 0 <= p and p < this->size();}inline bool _validate_index_in_closed([[maybe_unused]] const size_type p) const noexcept(NO_EXCEPT) {return 0 <= p and p <= this->size();}inline bool _validate_rigth_open_interval([[maybe_unused]] const size_type l, [[maybe_unused]] const size_type r) const noexcept(NO_EXCEPT) {return 0 <= l and l <= r and r <= this->size();}inline size_type _positivize_index(const size_type p) const noexcept(NO_EXCEPT) {return p < 0 ? this->size() + p : p;}public:valarray() noexcept(NO_EXCEPT) {}valarray(const size_type length, const T& val = T{}) noexcept(NO_EXCEPT) : std::valarray<T>(std::forward<const T>(val), length) {}template<class I, typename std::iterator_traits<I>::value_type* = nullptr>valarray(const I first, const I last) noexcept(NO_EXCEPT) : std::valarray<T>(first, last) {}template<class U> valarray(const std::initializer_list<U>& init) noexcept(NO_EXCEPT) : valarray(std::begin(init), std::end(init)) {}inline size_type size() const noexcept(NO_EXCEPT) { return this->std::valarray<T>::size(); }inline void reserve(const size_type) noexcept(NO_EXCEPT) { /* do nothing */ }template<class I, typename std::iterator_traits<I>::value_type* = nullptr>inline void assign(const I first, const I last) noexcept(NO_EXCEPT) {this->resize(std::distance(first, last));std::copy(first, last, begin(*this));}inline void assign(const size_type length, const T& val = T{}) noexcept(NO_EXCEPT) {this->std::valarray<T>::resize(length, val);}inline void resize(const size_type length, const T& val = T{}) noexcept(NO_EXCEPT) {std::valarray<T> temp = *this;this->assign(length, val);std::move(std::begin(temp), std::min(std::end(temp), std::next(std::begin(temp), length)), std::begin(*this));}inline const T& operator[](size_type pos) const noexcept(NO_EXCEPT) {pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos));return this->std::valarray<T>::operator[](pos);}inline T& operator[](size_type pos) noexcept(NO_EXCEPT) {pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos));return this->std::valarray<T>::operator[](pos);}inline const T& back() const noexcept(NO_EXCEPT) { return *std::prev(this->end()); }inline T& back() { return *std::prev(this->end()); }inline const T& front() const noexcept(NO_EXCEPT) { return *this->begin(); }inline T& front() { return *this->begin(); }inline const T* begin() const noexcept(NO_EXCEPT) { return this->size() ? std::addressof((*this)[0]) : nullptr; }inline T* begin() { return this->size() ? std::addressof((*this)[0]) : nullptr; }inline const T* end() const noexcept(NO_EXCEPT) { if(auto n = this->size()) { return std::addressof((*this)[0]) + n; } else { return nullptr; } }inline T* end() { if(auto n = this->size()) { return std::addressof((*this)[0]) + n; } else { return nullptr; } }};}
/* [adapter/valarray.hpp] */
namespace lib {namespace internal {namespace matrix_impl {template<class T> struct interface : virtual grid_impl::interface<T> {};}template<class T, class base>struct matrix_core : base, virtual matrix_impl::interface<T> {using base::base;static inline matrix_core identity(const size_t n, const T &&val = { 1 }) noexcept(NO_EXCEPT) {matrix_core res(n);REP(i, n) res(i, i) = val;return res;}inline size_t rows() const noexcept(NO_EXCEPT) /*override*/ { return this->height(); }inline size_t cols() const noexcept(NO_EXCEPT) /*override*/ { return this->width(); }inline size_t square() const noexcept(NO_EXCEPT) /*override*/ { return this->rows() == this->cols(); }template<class U> inline matrix_core& operator+=(const U rhs) noexcept(NO_EXCEPT) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) += rhs;return *this;}template<class ...U> inline matrix_core& operator+=(const matrix_core<U...> rhs) noexcept(NO_EXCEPT) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) += rhs(i, j);return *this;}template<class U> inline matrix_core operator+(const U rhs) const noexcept(NO_EXCEPT) {return matrix_core(*this) += rhs;}template<class U> inline matrix_core& operator-=(const U rhs) noexcept(NO_EXCEPT) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) -= rhs;return *this;}template<class ...U> inline matrix_core& operator-=(const matrix_core<U...> rhs) noexcept(NO_EXCEPT) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) -= rhs(i, j);return *this;}template<class U> inline matrix_core operator-(const U rhs) const noexcept(NO_EXCEPT) {return matrix_core(*this) -= rhs;}template<class ...U> inline matrix_core operator*(const matrix_core<U...> rhs) noexcept(NO_EXCEPT) {assert(this->cols() == rhs.rows());matrix_core res(this->rows(), rhs.cols());REP(i, this->rows()) REP(j, rhs.cols()) REP(k, this->cols()) {res(i, j) += (*this)(i, k) * rhs(k, j);}return res;}template<class U> inline matrix_core operator*(const U rhs) noexcept(NO_EXCEPT) {matrix_core res(*this);REP(i, res.rows()) REP(j, res.cols()) res(i, j) *= rhs;return res;}template<class U> inline matrix_core& operator*=(const U rhs) noexcept(NO_EXCEPT) {matrix_core res = *this * rhs;this->assign(res);return *this;}template<class U> inline matrix_core& operator/=(const U rhs) noexcept(NO_EXCEPT) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) /= rhs;return *this;}template<class U> inline matrix_core operator/(const U rhs) const noexcept(NO_EXCEPT) {return matrix_core(*this) /= rhs;}template<class U> inline matrix_core& operator%=(const U rhs) noexcept(NO_EXCEPT) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) %= rhs;return *this;}template<class U> inline matrix_core operator%(const U rhs) const noexcept(NO_EXCEPT) {return matrix_core(*this) %= rhs;}inline matrix_core pow(ll p) noexcept(NO_EXCEPT) {assert(this->square());matrix_core x = *this, res = matrix_core::Identity(this->rows());while(p > 0) {if(p & 1) res *= x;x *= x;p >>= 1;}return res;}};}template<class T, class base = grid<T>>using matrix = internal::matrix_core<T,base>;template<class T>using valmatrix = internal::matrix_core<T,unfolded_grid<T,valarray<T>>>;template<class T>using unfolded_matrix = internal::matrix_core<T,unfolded_grid<T>>;}
/* [numeric/matrix.hpp] */
/* #expanded [numeric/modint.hpp] */
#include <cassert>
#include <cstdint>
#include <atcoder/modint>
namespace lib {template <int _mod> using static_modint = atcoder::static_modint<_mod>;using modint998244353 = atcoder::modint998244353;using modint1000000007 = atcoder::modint1000000007;template <int id> using dynamic_modint = atcoder::dynamic_modint<id>;using modint = atcoder::modint;template<int> struct dynamic_modint_64bit;using modint64 = dynamic_modint_64bit<-1>;}namespace lib {template <int id> struct dynamic_modint_64bit : atcoder::internal::modint_base {private:using mint = dynamic_modint_64bit;using int64_t = std::int64_t;using uint64_t = std::uint64_t;using uint128_t = internal::uint128_t;protected:static uint64_t _mod;static uint64_t r;static uint64_t n2;static uint64_t get_r() noexcept(NO_EXCEPT) {uint64_t res = _mod;for(int64_t i = 0; i < 5; ++i)res *= 2 - _mod * res;return res;}static uint64_t reduce(const uint128_t &b) noexcept(NO_EXCEPT) {return (b + uint128_t(uint64_t(b) * uint64_t(-r)) * _mod) >> 64;}public:static uint64_t mod() noexcept(NO_EXCEPT) { return _mod; }static void set_mod(const uint64_t m) noexcept(NO_EXCEPT) {assert(m < (1UL << 63));assert((m & 1) == 1);_mod = m;n2 = -static_cast<uint128_t>(m) % m;r = get_r();assert(r * _mod == 1);}uint64_t _val;dynamic_modint_64bit() noexcept(NO_EXCEPT) : _val(0) {}dynamic_modint_64bit(const std::int64_t b) noexcept(NO_EXCEPT): _val(this->reduce((static_cast<uint128_t>(b) + this->_mod) * this->n2)) {};mint &operator+=(const mint &b) noexcept(NO_EXCEPT) {if(static_cast<int64_t>(_val += b._val - 2 * _mod) < 0) this->_val += 2 * this->_mod;return *this;}mint &operator-=(const mint &b) noexcept(NO_EXCEPT) {if(static_cast<int64_t>(this->_val -= b._val) < 0)this->_val += 2 * this->_mod;return *this;}mint &operator*=(const mint &b) noexcept(NO_EXCEPT) {this->_val = reduce(static_cast<uint128_t>(this->_val) * b._val);return *this;}mint &operator/=(const mint &b) noexcept(NO_EXCEPT) {*this *= b.inv();return *this;}mint operator+(const mint &b) const noexcept(NO_EXCEPT) { return mint(*this) += b; }mint operator-(const mint &b) const noexcept(NO_EXCEPT) { return mint(*this) -= b; }mint operator*(const mint &b) const noexcept(NO_EXCEPT) { return mint(*this) *= b; }mint operator/(const mint &b) const noexcept(NO_EXCEPT) { return mint(*this) /= b; }bool operator==(const mint &b) const noexcept(NO_EXCEPT) {return (this->_val >= this->_mod ? this->_val - this->_mod : this->_val) == (b._val >= this->_mod ? b._val - this->_mod : b._val);}bool operator!=(const mint &b) const noexcept(NO_EXCEPT) {return (this->_val >= this->_mod ? this->_val - this->_mod : this->_val) != (b._val >= this->_mod ? b._val - this->_mod : b._val);}mint operator-() const noexcept(NO_EXCEPT) { return mint{} - static_cast<mint>(*this); }mint pow(uint128_t n) const noexcept(NO_EXCEPT) {mint res(1), mul(*this);while(n > 0) {if(n & 1)res *= mul;mul *= mul;n >>= 1;}return res;}mint inv() const noexcept(NO_EXCEPT) { return this->pow(this->_mod - 2); }uint64_t val() const noexcept(NO_EXCEPT) {uint64_t res = this->reduce(this->_val);return res >= this->_mod ? res - this->_mod : res;}};template<int id> typename dynamic_modint_64bit<id>::uint64_t dynamic_modint_64bit<id>::_mod;template<int id> typename dynamic_modint_64bit<id>::uint64_t dynamic_modint_64bit<id>::r;template<int id> typename dynamic_modint_64bit<id>::uint64_t dynamic_modint_64bit<id>::n2;}
/* [numeric/modint.hpp] */
/* #expanded [constants.hpp] */
#include <cstdint>
#include <utility>
#include <limits>
namespace lib {i32 INF32 = (std::numeric_limits<i32>::max() >> 1) - 1;i64 INF64 = (std::numeric_limits<i64>::max() >> 1) - 1;constexpr char LN = '\n';constexpr char SPC = ' ';constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };enum class comp : std::int8_t {equal_to,not_equal_to,equals = equal_to,eq = equal_to,under,over,or_under,or_over,less = under,more = over,less_than = under,more_than = over,not_less_than = or_over,not_more_than = or_under,leq = or_under,geq = or_over};enum class interval : std::int8_t {right_open,left_open,open,closed,};}
/* [constants.hpp] */
/* #expanded [multi_container.hpp] */
#include <cassert>
#include <vector>
#include <array>
/* #expanded [internal/exception.hpp] */
namespace lib {namespace internal {template<class... T> constexpr bool EXCEPTION = false;template<const int T> constexpr bool EXCEPTION_INT = false;}}
/* [internal/exception.hpp] */
namespace lib {namespace internal {namespace multi_container_impl {template<class container> struct base : container {using container::container;protected:inline void _validate_index(__attribute__ ((unused)) const internal::size_t index) const noexcept(NO_EXCEPT) {assert(0 <= index and index < (internal::size_t)this->size());}inline internal::size_t _positivize_index(const internal::size_t x) const noexcept(NO_EXCEPT) {return x < 0 ? this->size() + x : x;}};}}template<class T, const unsigned int RANK, template<class...> class container = valarray>struct multi_container : internal::multi_container_impl::base<container<multi_container<T,RANK-1,container>>> {using internal::multi_container_impl::base<container<multi_container<T,RANK-1,container>>>::base;template<class Head, class... Tail>multi_container(const Head head, const Tail... tail) noexcept(NO_EXCEPT): internal::multi_container_impl::base<container<multi_container<T,RANK-1,container>>>(head, multi_container<T,RANK-1,container>(tail...)) {static_assert(std::is_integral_v<Head>, "size must be integral");}template<class Head, class... Tail> T& operator()(const Head _head, const Tail... tail) noexcept(NO_EXCEPT) {static_assert(std::is_integral_v<Head>, "index must be integral");const internal::size_t head = this->_positivize_index(_head);this->_validate_index(head);return (*this)[head](tail...);}template<class Head, class... Tail> const T& operator()(const Head _head, const Tail... tail) const noexcept(NO_EXCEPT) {static_assert(std::is_integral_v<Head>, "index must be integral");const internal::size_t head = this->_positivize_index(_head);this->_validate_index(head);return (*this)[head](tail...);}};template<class T, template<class...> class container>struct multi_container<T,1,container> : internal::multi_container_impl::base<container<T>> {using internal::multi_container_impl::base<container<T>>::base;template<class... Args> multi_container(const Args&... args) noexcept(NO_EXCEPT) : internal::multi_container_impl::base<container<T>>(args...) {}T& operator()(const internal::size_t _index) noexcept(NO_EXCEPT) {const internal::size_t index = this->_positivize_index(_index);this->_validate_index(index);return (*this)[index];}const T& operator()(const internal::size_t _index) const noexcept(NO_EXCEPT) {const internal::size_t index = this->_positivize_index(_index);this->_validate_index(index);return (*this)[index];}};template<class T, template<class...> class container>struct multi_container<T,0,container> {static_assert(internal::EXCEPTION<T>, "invalid rank: 0, should be 1 or more");};}
/* [multi_container.hpp] */
/* #expanded [graph.hpp] */
#include <cassert>
#include <tuple>
#include <vector>
#include <iostream>
/* #expanded [data_structure/disjoint_set_union.hpp] */
#include <cassert>
#include <algorithm>
#include <cassert>
#include <vector>
namespace lib {struct dsu {using size_type = internal::size_t;private:size_type _n, _group_count;mutable std::vector<size_type> _parent_or_size;public:dsu() noexcept(NO_EXCEPT) : _n(0) {}explicit dsu(const size_type n) noexcept(NO_EXCEPT) : _n(n), _group_count(n), _parent_or_size(n, -1) {}inline size_type size() const noexcept(NO_EXCEPT) { return this->_n; }inline size_type group_count() const noexcept(NO_EXCEPT) { return this->_group_count; }inline size_type merge(const size_type a, const size_type b) noexcept(NO_EXCEPT) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);size_type x = this->leader(a), y = this->leader(b);if (x == y) return x;--this->_group_count;if (-this->_parent_or_size[x] < -this->_parent_or_size[y]) std::swap(x, y);this->_parent_or_size[x] += this->_parent_or_size[y];this->_parent_or_size[y] = x;return x;}inline bool same(const size_type a, const size_type b) const noexcept(NO_EXCEPT) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);return this->leader(a) == this->leader(b);}inline size_type leader(const size_type a) const noexcept(NO_EXCEPT) {assert(0 <= a && a < _n);if (_parent_or_size[a] < 0) return a;return _parent_or_size[a] = this->leader(_parent_or_size[a]);}inline size_type size(const size_type a) const noexcept(NO_EXCEPT) {assert(0 <= a && a < _n);return -_parent_or_size[this->leader(a)];}inline std::vector<std::vector<size_type>> groups() const noexcept(NO_EXCEPT) {std::vector<size_type> leader_buf(_n), group_size(_n);for (size_type i = 0; i < _n; i++) {leader_buf[i] = this->leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<size_type>> result(_n);for (size_type i = 0; i < _n; i++) {result[i].reserve(group_size[i]);}for (size_type i = 0; i < _n; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(),[&](const std::vector<size_type>& v) { return v.empty(); }),result.end());return result;}};}
/* [data_structure/disjoint_set_union.hpp] */
namespace lib {namespace internal {namespace graph_impl {template<class cost_t, class size_type> struct edge {private:inline static internal::size_t unique() noexcept(NO_EXCEPT) { static internal::size_t id = 0; return id++; }public:using cost_type = cost_t;const internal::size_t id = unique();const size_type from, to; const cost_t cost;edge(const size_type u, const size_type v, const cost_t w) noexcept(NO_EXCEPT) : from(u), to(v), cost(w) {}operator size_type() const noexcept(NO_EXCEPT) { return this->to; }inline size_type opposite(const size_type v) const noexcept(NO_EXCEPT) {if(this->from == v) return this->to;if(this->to == v) return this->from;assert(false);}std::tuple<size_type,size_type,cost_t> _debug() const noexcept(NO_EXCEPT) { return { from, to, cost }; };friend bool operator==(const edge& lhs, const edge& rhs) noexcept(NO_EXCEPT) { return lhs.id == rhs.id; }friend bool operator!=(const edge& lhs, const edge& rhs) noexcept(NO_EXCEPT) { return lhs.id != rhs.id; }};}}template<class C = ll>struct graph : std::vector<std::vector<internal::graph_impl::edge<C,internal::size_t>>> {using size_type = internal::size_t;using cost_type = C;using edge_type = typename internal::graph_impl::edge<cost_type,size_type>;enum class edge_kind { undirected, directed };private:size_type _directed_edge_count = 0, _undirected_edge_count = 0;std::vector<edge_type> _edges;std::vector<size_type> _out_degs, _in_degs;protected:inline void _add_edge(const size_type u, const size_type v, const cost_type w) noexcept(NO_EXCEPT) {this->operator[](u).emplace_back(u, v, w);++_out_degs[u], ++_in_degs[v];++this->_directed_edge_count;}public:explicit graph(const size_type n = 0) noexcept(NO_EXCEPT): std::vector<std::vector<edge_type>>(n), _out_degs(n), _in_degs(n){}inline void clear() noexcept(NO_EXCEPT) { this->std::vector<std::vector<edge_type>>::clear(); }inline const auto& edges() const noexcept(NO_EXCEPT) { return this->_edges; }inline const auto& edge(const size_type k) const noexcept(NO_EXCEPT) { return this->_edges[k]; }inline const auto& degrees() const noexcept(NO_EXCEPT) { return this->_in_degs; }inline const auto& degree(const size_type k) const noexcept(NO_EXCEPT) { return this->_in_degs[k]; }inline const auto& in_degrees() const noexcept(NO_EXCEPT) { return this->_in_degs; }inline const auto& in_degree(const size_type k) const noexcept(NO_EXCEPT) { return this->_in_degs[k]; }inline const auto& out_degrees() const noexcept(NO_EXCEPT) { return this->_out_degs; }inline const auto& out_degree(const size_type k) const noexcept(NO_EXCEPT) { return this->_out_degs[k]; }inline size_type vertices() const noexcept(NO_EXCEPT) { return this->size(); }inline size_type directed_edges_count() const noexcept(NO_EXCEPT) { return this->_directed_edge_count; }template<const edge_kind EDGE_TYPE = edge_kind::directed>inline void add_edge(const size_type u, const size_type v, const cost_type w = 1) noexcept(NO_EXCEPT) {assert(0 <= u and u < this->vertices()), assert(0 <= v and v < this->vertices());this->_edges.emplace_back(u, v, w);this->_add_edge(u, v, w);if constexpr(EDGE_TYPE == edge_kind::undirected) this->_add_edge(v, u, w);}inline void add_edge_bidirectionally(const size_type u, const size_type v, const cost_type w = 1) noexcept(NO_EXCEPT) {this->add_edge<edge_kind::undirected>(u, v, w);}template<bool WEIGHTED = false, bool ONE_ORIGIN = true, const edge_kind EDGE_TYPE = edge_kind::directed, class Stream = std::istream>void inline read(const size_type edges, Stream *const ist = &std::cin) noexcept(NO_EXCEPT) {REP(edges) {size_type u, v; cost_type w = 1; *ist >> u >> v; if(ONE_ORIGIN) --u, --v;if(WEIGHTED) *ist >> w;this->add_edge<EDGE_TYPE>(u, v, w);}}template<bool WEIGHTED = false, bool ONE_ORIGIN = true, class Stream = std::istream>void inline read_bidirectionally(const size_type edges, Stream *const ist = &std::cin) noexcept(NO_EXCEPT) {REP(edges) {size_type u, v; cost_type w = 1; *ist >> u >> v; if(ONE_ORIGIN) --u, --v;if(WEIGHTED) *ist >> w;this->add_edge<edge_kind::undirected>(u, v, w);}}template<class cost_t = cost_type> inline void distances_without_cost(const size_type, std::vector<cost_t> *const) const noexcept(NO_EXCEPT) ;template<class cost_t = cost_type> inline std::vector<cost_t> distances_without_cost(const size_type) const noexcept(NO_EXCEPT) ;template<class cost_t = cost_type> inline void distances_with_01cost(const size_type, std::vector<cost_t> *const) const noexcept(NO_EXCEPT) ;template<class cost_t = cost_type> inline std::vector<cost_t> distances_with_01cost(const size_type) const noexcept(NO_EXCEPT) ;template<class cost_t = cost_type> inline void distances(const size_type, std::vector<cost_t> *const) const noexcept(NO_EXCEPT) ;template<class cost_t = cost_type> inline std::vector<cost_t> distances(const size_type) const noexcept(NO_EXCEPT) ;inline bool sort_topologically(std::vector<size_type> *const ) const noexcept(NO_EXCEPT) ;inline bool sort_topologically() const noexcept(NO_EXCEPT) ;template<class> inline bool sort_topologically_with_priority(std::vector<size_type> *const) const noexcept(NO_EXCEPT) ;template<class> inline bool sort_topologically_with_priority() const noexcept(NO_EXCEPT) ;inline size_type minimum_paph_cover_size_as_dag() const noexcept(NO_EXCEPT) ;template<class cost_t = cost_type>inline cost_t minimum_spanning_tree(graph *const = nullptr) const noexcept(NO_EXCEPT) ;template<class cost_t = cost_type>inline cost_t maximum_spanning_tree(graph *const = nullptr) const noexcept(NO_EXCEPT) ;inline dsu components() const noexcept(NO_EXCEPT) ;template<bool = false, class G, class U = char>inline void from_grid(const G&, U = '.') noexcept(NO_EXCEPT) ;template<class I, class J = I, class distance_type = cost_type, class = internal::size_t>inline distance_type build_manhattan_mst(const I, const I, const J, const J) noexcept(NO_EXCEPT) ;};}
/* [graph.hpp] */
/* #expanded [string.hpp] */
#include <string>
#include <iterator>
namespace lib {template<class I, class Res = std::string>Res to_lower(const I first, const I last) noexcept(NO_EXCEPT) {Res res;res.reserve(std::distance(first, last));std::transform(first, last, std::back_inserter(res), ::tolower);return res;}template<class I, class Res = std::string>Res to_uppwer(const I first, const I last) noexcept(NO_EXCEPT) {Res res;res.reserve(std::distance(first, last));std::transform(first, last, std::back_inserter(res), ::toupper);return res;}template<class Res = std::string>Res to_lower(const std::string str) noexcept(NO_EXCEPT) {return to_lower<std::string::const_iterator,Res>(std::begin(str), std::end(str));}template<class Res = std::string>Res to_uppwer(const std::string str) noexcept(NO_EXCEPT) {return to_uppwer<std::string::const_iterator,Res>(std::begin(str), std::end(str));}}
/* [string.hpp] */
/* #expanded [adapter/set.hpp] */
#include <set>
#include <unordered_set>
#include <iterator>
#include <optional>
/* #expanded [utility/functional.hpp] */
#include <functional>
#include <utility>
namespace lib {namespace internal {template<class T> constexpr T plus(const T a, const T b) { return std::plus<T>{}(a, b); }template<class T> constexpr T minus(const T a, const T b) { return std::minus<T>{}(a, b); }template<class T> constexpr T bitxor(const T a, const T b) { return a xor b; }}template<class T1, class T2> inline auto mod(T1 x, T2 r) { return (x%r+r)%r; }template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return (a<b ? a=b, true : false); }template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { return (a>b ? a=b, true : false); }template<class T> inline constexpr T sign(const T x) {return (x > 0) - (x < 0);}template<class T, T FROM_MIN, T FROM_MAX, T TO_MIN, T TO_MAX> inline constexpr T mapping(const T x) {return (x - FROM_MIN) * (TO_MAX - TO_MIN) / (FROM_MAX - FROM_MIN) + TO_MIN;}template<class T> inline constexpr T mapping(const T x, const T from_min, const T from_max, const T to_min, const T to_max) {return (x - from_min) * (to_max - to_min) / (from_max - from_min) + to_min;}}
/* [utility/functional.hpp] */
namespace lib {namespace internal {template<class set> struct set_wrapper : set {using set::set;using size_type = internal::size_t;inline size_type size() const noexcept(NO_EXCEPT) { return this->set::size(); }inline bool contains(const typename set::key_type& key) noexcept(NO_EXCEPT) { return static_cast<bool>(this->count(key)); }inline std::optional<typename set::iterator> remove(const typename set::key_type& key) noexcept(NO_EXCEPT) {const auto itr = this->find(key);if(itr == this->set::end()) return {};return this->erase(itr);}inline auto min_element() noexcept(NO_EXCEPT) { return this->begin(); }inline auto max_element() noexcept(NO_EXCEPT) { return this->begin(); }inline auto min() noexcept(NO_EXCEPT) { return *this->begin(); }inline auto max() noexcept(NO_EXCEPT) { return *this->end(); }inline auto pop_min() noexcept(NO_EXCEPT) { this->erase(this->begin()); return *this; }inline auto pop_max() noexcept(NO_EXCEPT) { this->erase(this->end()); return *this; }inline auto next_element(const typename set::key_type& key, const size_type _count = 0) noexcept(NO_EXCEPT) {size_type count = std::abs(_count);auto itr = this->lower_bound(key);const auto begin = this->begin(), end = this->end();if(itr == end) return this->end();if(itr == begin) return this->begin();while(count--) {if(_count < 0) if(itr-- == begin) return this->begin();if(_count > 0) if(++itr == end) return this->end();}return itr;}inline auto prev_element(const typename set::key_type& key, const size_type _count = 0) noexcept(NO_EXCEPT) {size_type count = std::abs(_count);auto itr = this->upper_bound(key);const auto begin = this->begin(), end = this->end();if(itr == end) return this->end();if(itr-- == begin) return this->begin();while(count--) {if(_count < 0) if(itr-- == begin) return this->begin();if(_count > 0) if(++itr == end) return this->end();}return itr;}inline std::optional<typename set::value_type> next(const typename set::key_type& key, size_type count = 0) noexcept(NO_EXCEPT) {auto itr = this->lower_bound(key);const auto end = this->end();if(itr == end) return {};while(count--) if(++itr == end) return {};return { *itr };}inline std::optional<typename set::value_type> prev(const typename set::key_type& key, size_type count = 0) noexcept(NO_EXCEPT) {auto itr = this->upper_bound(key);const auto begin = this->begin();if(itr-- == begin) return {};while(count--) if(itr-- == begin) return {};return { *itr };}friend inline set_wrapper operator|(const set_wrapper s, const set_wrapper t) noexcept(NO_EXCEPT) {set_wrapper res;std::set_union(std::begin(s), std::end(s), std::begin(t), std::end(t), std::inserter(res, std::begin(res)));return res;}};}template<class... Args> using set = internal::set_wrapper<std::set<Args...>>;template<class... Args> using unordered_set = internal::set_wrapper<std::unordered_set<Args...>>;template<class... Args> using multiset = internal::set_wrapper<std::multiset<Args...>>;template<class... Args> using unordered_multiset = internal::set_wrapper<std::unordered_multiset<Args...>>;}
/* [adapter/set.hpp] */
/* #expanded [adapter/vector.hpp] */
#include <vector>
#include <algorithm>
namespace lib {template<class T>struct vector : std::vector<T> {using std::vector<T>::vector;inline auto& sort() noexcept(NO_EXCEPT) {std::sort(this->begin(), this->end());return *this;}template<class F>inline auto& sort(const F&& f) noexcept(NO_EXCEPT) {std::sort(this->begin(), this->end(), f);return *this;}};}
/* [adapter/vector.hpp] */
/* #expanded [utility/applier.hpp] */
#include <utility>
#include <algorithm>
namespace lib {namespace internal {template<class T> T max(T a, T b) { return std::max(a, b); }template<class T> T max(T x) { return x; }template<class T> T max() { return -std::numeric_limits<T>::min(); }template<class T> T min(T a, T b) { return std::min(a, b); }template<class T> T min(T x) { return x; }template<class T> T min() { return std::numeric_limits<T>::max(); }}template<class T, T (*op)(T,T)> struct applier {using value_type = T;protected:T _v;public:applier(const T& v = T{}) : _v(v) {}template<class U> applier& operator<<=(U&& val) & noexcept {_v = op(_v, std::forward<U>(val));return *this;}inline T val() const { return _v; }inline operator T() const { return _v; }};template<class T> using maximum = applier<T,internal::max<T>>;template<class T> using minimum = applier<T,internal::min<T>>;}
/* [utility/applier.hpp] */
/* #expanded [utility/restrictor.hpp] */
#include <utility>
namespace lib {template<class T, T INF, T SUP> struct static_restrictor {using restrictor = static_restrictor;protected:T _v;inline void _clamp() { this->_v = std::clamp(this->_v, INF, SUP); }inline restrictor& _assign(T v) {this->_v = std::clamp(v, INF, SUP);return *this;}public:static_restrictor(T v = T{}) : _v(v) {}inline T val() const { return this->_v; }restrictor& operator++() { return this->_assign(this->_v + 1); }restrictor& operator--() { return this->_assign(this->_v - 1); }restrictor operator++(int) {restrictor res = *this;*this++;return res;}restrictor operator--(int) {restrictor res = *this;*this--;return res;}restrictor& operator+=(const restrictor& rhs) { return this->_assign(this->_v + rhs.val()); }restrictor& operator-=(const restrictor& rhs) { return this->_assign(this->_v - rhs.val()); }restrictor& operator*=(const restrictor& rhs) {if(mul_over(this->_v, rhs.val(), SUP)) return this->_assign(SUP);if(mul_under(this->_v, rhs.val(), INF)) return this->_assign(INF);return this->_assign(this->_v * rhs.val());}restrictor& operator/=(const restrictor& rhs) { return this->_assign(this->_v / rhs.val()); }restrictor operator+() const { return *this; }restrictor operator-() const { return restrictor() - *this; }friend restrictor operator+(const restrictor& lhs, const restrictor& rhs) {return restrictor(lhs) += rhs;}friend restrictor operator-(const restrictor& lhs, const restrictor& rhs) {return restrictor(lhs) -= rhs;}friend restrictor operator*(const restrictor& lhs, const restrictor& rhs) {return restrictor(lhs) *= rhs;}friend restrictor operator/(const restrictor& lhs, const restrictor& rhs) {return restrictor(lhs) /= rhs;}friend bool operator==(const restrictor& lhs, const restrictor& rhs) {return lhs._v == rhs._v;}friend bool operator!=(const restrictor& lhs, const restrictor& rhs) {return lhs._v != rhs._v;}friend bool operator<(const restrictor& lhs, const restrictor& rhs) {return lhs._v < rhs._v;}friend bool operator>(const restrictor& lhs, const restrictor& rhs) {return lhs._v > rhs._v;}friend bool operator<=(const restrictor& lhs, const restrictor& rhs) {return lhs._v <= rhs._v;}friend bool operator>=(const restrictor& lhs, const restrictor& rhs) {return lhs._v >= rhs._v;}};}namespace std {template<class T, T INF, T SUP>T std::abs(const lib::static_restrictor<T,INF,SUP>& v) { return std::abs(v.val()); }}
/* [utility/restrictor.hpp] */
/* #expanded [iterable/applied.hpp] */
#include <algorithm>
#include <vector>
#include <iterator>
namespace lib {template<class I, class F, class C = std::vector<typename std::iterator_traits<I>::value_type>>inline auto applied(const I first, const I last, F&& func) noexcept(NO_EXCEPT) {C res(first, last);func(std::begin(res), std::end(res));return res;}template<class V, class F, class C = V>inline auto applied(V v, F&& func) noexcept(NO_EXCEPT) {return applied<typename V::iterator,F,C>(std::begin(v), std::end(v), func);}template<class I>inline auto sorted(const I first, const I last) noexcept(NO_EXCEPT) {return applied(first, last, std::sort<I>);}template<class V>inline auto sorted(V v) noexcept(NO_EXCEPT) {return applied(v, std::sort<typename V::iterator>);}template<class I>inline auto reversed(const I first, const I last) noexcept(NO_EXCEPT) {return applied(first, last, std::reverse<I>);}template<class V>inline auto reversed(V v) noexcept(NO_EXCEPT) {return applied(v, std::reverse<typename V::iterator>);}}
/* [iterable/applied.hpp] */
/* #expanded [iterable/accumulation.hpp] */
#include <cassert>
#include <iterator>
#include <vector>
#include <functional>
#include <numeric>
namespace lib {template<class T = i64, class container = valarray<T>>struct accumulation : container {using size_type = internal::size_t;protected:inline size_type _positivize_index(const size_type x) const noexcept(NO_EXCEPT) {return x < 0 ? std::size(*this) + x : x;}public:accumulation() noexcept(NO_EXCEPT) {}template<class I, class Operator = std::plus<T>>accumulation(const I first, const I last, const T head = T{}, const Operator op = std::plus<T>{}) noexcept(NO_EXCEPT) {this->assign(std::distance(first, last) + 1, {});std::exclusive_scan(first, last, std::begin(*this), head, op);if(this->size() > 1) *std::prev(this->end()) = op(*std::prev(std::end(*this), 2), *std::prev(last));}template<class Operaotr = std::minus<T>>inline T operator()(size_type left, size_type right, Operaotr op = std::minus<T>{}) const noexcept(NO_EXCEPT) {left = _positivize_index(left), right = _positivize_index(right);assert(0 <= left and left <= right and right < (size_type)std::size(*this));return op((*this)[right], (*this)[left]);}};template<class T, class container = valarray<valarray<T>>, class Operator = std::plus<T>>struct accumulation_2d : container {using size_type = internal::size_t;protected:inline size_type _positivize_index(const size_type x) const noexcept(NO_EXCEPT) {return x < 0 ? std::size(*this) + x : x;}Operator _op;public:accumulation_2d() noexcept(NO_EXCEPT) {}template<class I>accumulation_2d(const I first, const I last, const T head = T{}, const Operator op = std::plus<T>{}) noexcept(NO_EXCEPT) : _op(op) {const size_type h = std::distance(first, last);const size_type w = std::distance(std::begin(*first), std::end(*first));{auto row = first;this->assign(h+1, head);(*this)[0].assign(w+1, head);REP(i, h) {assert(w == std::distance(std::begin(*row), std::end(*row)));(*this)[i+1].assign(w+1, head);REP(j, w) (*this)[i+1][j+1] = first[i][j];++row;}}FOR(i, 1, h) FOR(j, w) (*this)[i][j] = op((*this)[i][j], (*this)[i-1][j]);FOR(i, h) FOR(j, 1, w) (*this)[i][j] = op((*this)[i][j], (*this)[i][j-1]);}template<class Rev = std::minus<T>>inline T operator()(size_type a, size_type b, size_type c, size_type d, const Rev rev = std::minus<T>{}) const noexcept(NO_EXCEPT) {a = _positivize_index(a), b = _positivize_index(b);c = _positivize_index(c), d = _positivize_index(d);assert(0 <= a and a <= b and b < (size_type)std::size(*this));assert(0 <= c and c <= d and d < (size_type)std::size((*this)[0]));return this->_op(rev((*this)[b][d], this->_op((*this)[a][d], (*this)[b][c])), (*this)[a][c]);}template<class Rev = std::minus<T>>inline T operator()(const std::pair<size_type,size_type> p, const std::pair<size_type,size_type> q, const Rev rev = std::minus<T>{}) const noexcept(NO_EXCEPT) {return this->operator()(p.first, p.second, q.first, q.second, rev);}};}
/* [iterable/accumulation.hpp] */
/* #expanded [iterable/operation.hpp] */
#include <string>
#include <iterator>
#include <numeric>
namespace lib {template<class I>std::string join(const I first, const I last, const std::string& sep = "") noexcept(NO_EXCEPT) {std::ostringstream res;std::copy(first, last, std::ostream_iterator<typename std::iterator_traits<I>::value_type>(res, sep));return res.str();}template<class V>std::string join(V& v, const std::string& sep = "") noexcept(NO_EXCEPT) {return join(std::begin(v), std::end(v), sep);}template<class I, class T = typename std::iterator_traits<I>::value_type>T sum(const I first, const I second, const T& base = 0) noexcept(NO_EXCEPT) {return std::accumulate(first, second, base);}template<class V, class T = typename V::value_type>auto sum(V& v, T base = 0) noexcept(NO_EXCEPT) {return sum(std::begin(v), std::end(v), base);}}
/* [iterable/operation.hpp] */
/* #expanded [iterable/mex.hpp] */
#include <iterator>
#include <algorithm>
namespace lib {template<class I, class T = typename std::iterator_traits<I>::value_type>T mex(const I first, const I last, const T& base = 0) noexcept(NO_EXCEPT) {std::vector<T> val(first, last);std::sort(val.begin(), val.end());val.erase(std::unique(val.begin(), val.end()), val.end());val.erase(val.begin(), std::lower_bound(val.begin(), val.end(), base));internal::size_t i = 0;while(i < (internal::size_t)val.size() and val[i] == T{i} + base) ++i;return T{i} + base;}template<class V, class T = typename V::value_type>auto mex(const V v, const T& base = 0) noexcept(NO_EXCEPT) {return mex(v.begin(), v.end(), base);}}
/* [iterable/mex.hpp] */
/* [utilities.hpp] */
using std::cin;using std::cout;using std::pair;using std::tuple;using std::array;using std::string;using std::queue;using std::stack;using std::priority_queue;using std::bitset;using std::sort;using std::reverse;using std::map;using std::unordered_map;using std::min_element;using std::max_element;using lib::i32;using lib::u32;using lib::i64;using lib::u64;
#ifdef __GNUC__
using lib::i128;using lib::u128;
#endif
using lib::uint;using lib::ll;using lib::ull;using lib::ld;using lib::INF32;using lib::INF64;using lib::LN;using lib::SPC;using lib::DIRS4;using lib::DIRS8;using lib::nPr;using lib::nCr;using lib::pow;using lib::pow_mod;using lib::inv_mod;using lib::spair;using lib::multi_container;using lib::minimum;using lib::maximum;using lib::modint998244353;using lib::modint1000000007;using lib::modint;using lib::modint64;using lib::sorted;using lib::reversed;using lib::join;using lib::chmin;using lib::chmax;using lib::grid;using lib::graph;using lib::matrix;using lib::unordered_multiset;using lib::set;using lib::unordered_set;using lib::multiset;using lib::unordered_multiset;using lib::valarray;using lib::vector;
/* [snippet/using.hpp] */
#ifdef LOCAL_JUDGE
#include<debug>
#define debug(...) debugger::debug(debugger::split(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#define DEBUG(...) do { debugger::DEBUG(nullptr, "\033[3;35m#" + std::to_string(__LINE__) + "\033[m "); debugger::DEBUG(__VA_ARGS__); debugger::DEBUG(nullptr, "\033[m\n"); } while(0);
#else
#define debug(...) ({ ; })
#define DEBUG(...) ({ ; })
#endif
/* #expanded [adapter/input.hpp] */
#include <atcoder/modint>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
/* #expanded [internal/resolving_rank.hpp] */
namespace lib {namespace internal {template<int P> struct resolving_rank : resolving_rank<P-1> {};template<> struct resolving_rank<0> {};}}
/* [internal/resolving_rank.hpp] */
template<class source = std::istream>struct input_adapter {private:template<class T>auto _set(lib::internal::resolving_rank<3>, T *const val) noexcept(NO_EXCEPT) -> decltype(std::declval<source&>() >> *val, 0) {*this->in >> *val;return 0;}template<class T>auto _set(lib::internal::resolving_rank<2>, T *const val) noexcept(NO_EXCEPT) -> decltype(std::begin(*val), std::end(*val), 0) {(*this)(std::begin(*val), std::end(*val));return 0;}template<class T>auto _set(lib::internal::resolving_rank<1>, T *const val) noexcept(NO_EXCEPT) -> decltype(val->first, val->second, 0) {(*this)(&*val);return 0;}template<class T>auto _set(lib::internal::resolving_rank<0>, T *const val) noexcept(NO_EXCEPT) -> std::enable_if_t<atcoder::internal::is_modint<T>::value,int> {long long v; std::cin >> v;*val = { v };return 0;}protected:template<class T>source *set(T *const val) noexcept(NO_EXCEPT) {this->_set(lib::internal::resolving_rank<3>{}, val);return this->in;}public:using char_type = typename source::char_type;source *in;input_adapter(source *in = &std::cin) noexcept(NO_EXCEPT) : in(in) {}template<class T> inline input_adapter& operator>>(T &s) noexcept(NO_EXCEPT) {this->set(&s);return *this;}template<class T> inline T one() noexcept(NO_EXCEPT) {T val; *this >> val;return val;}template<class T> inline void operator()(T*const val) noexcept(NO_EXCEPT) {*this >> *val;}template<class T, class... Args> inline void operator()(T *const head, Args *const... tail) noexcept(NO_EXCEPT) {*this >> *head;(*this)(tail...);}template<class I, class = typename std::iterator_traits<I>::value_type> inline void operator()(I first, I last) noexcept(NO_EXCEPT) {for(I itr=first; itr!=last; ++itr) *this >> *itr;}template<class F, class S> inline void operator()(std::pair<F,S> *const p) noexcept(NO_EXCEPT) {*this >> p->first >> p->second;}};
/* [adapter/input.hpp] */
/* #expanded [adapter/output.hpp] */
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <iterator>
template<class destination = std::ostream, class Terminator = std::string, class Separator = std::string>struct output_adapter {private:template<class T>auto _put(lib::internal::resolving_rank<2>, const T &val) noexcept(NO_EXCEPT)-> decltype(std::declval<destination&>() << val, 0) {*this->out << val;return 0;}template<class T>auto _put(lib::internal::resolving_rank<1>, const T &val) noexcept(NO_EXCEPT)-> decltype(val.val(), 0) {this->put(val.val());return 0;}template<class T>auto _put(lib::internal::resolving_rank<0>, const T &val) noexcept(NO_EXCEPT)-> decltype(std::begin(val), std::end(val), 0) {(*this)(std::begin(val), std::end(val), false);return 0;}protected:template<class T>destination *put(const T &val) noexcept(NO_EXCEPT){this->_put(lib::internal::resolving_rank<2>{}, val);return this->out;}public:using char_type = typename destination::char_type;static constexpr auto sendl = std::endl<char_type,std::char_traits<char_type>>;destination *out;Terminator endline;Separator separator;output_adapter(destination *out = &std::cout, Terminator endline = "\n", Separator separator = " ") noexcept: out(out), endline(endline), separator(separator){*this << std::fixed << std::setprecision(20);}inline void seekp(const typename destination::off_type off, const std::ios_base::seekdir dir = std::ios_base::cur) noexcept(NO_EXCEPT){ this->out->seekp(off, dir); };template<class T> inline output_adapter& operator<<(const T &s) noexcept(NO_EXCEPT){this->put(s);return *this;}template<class T = std::string> inline void operator()(const T &val = "") noexcept(NO_EXCEPT){*this << val << this->endline;}template<class T, class ...Args> inline void operator()(const T &head, const Args& ...tail) noexcept(NO_EXCEPT){*this << head << this->separator;(*this)(tail...);}template<class I, class = typename std::iterator_traits<I>::iterator_category> inline void operator()(const I first, const I last, const bool terminate = true) noexcept(NO_EXCEPT){for(I itr=first; itr!=last;) {*this << *itr;if(++itr == last) {if(terminate) *this << this->endline;}else *this << this->separator;}}template<class T> inline void operator()(const std::initializer_list<T> vals) noexcept(NO_EXCEPT){std::vector wrapped(vals.begin(), vals.end());(*this)(wrapped.begin(), wrapped.end());}template<class F, class S> inline void operator()(const std::pair<F,S> &p) noexcept(NO_EXCEPT){(*this)(p.first, p.second);}};
/* [adapter/output.hpp] */
input_adapter _input;output_adapter _print;
#define input _input
#define print _print
/* [template.hpp] */
/* #endregion */

void solve();

signed main() {
    int $ = 1;
    // std::cin >> $;
    for(int _ = 0; _ < $; ++_) {
        DEBUG("Case: #" + std::to_string(_));
        solve();
    }
    return 0;
}

void solve() {
    i64 n, m, p, q; cin >> n >> m >> p >> q;
    i64 a = m % p;

    REP(q) {
        i64 x, f; cin >> x >> f;
        debug(x, f);

        i64 t = x % p;
        if(t == 0) {
            if(f == 0) print(m);
            else print(0);
        }
        else {
            i64 v = (f * lib::inv_mod(x, p)) % p;
            debug(v);
            print(m / p + (v <= a and v%p != 0));
        }
    }
}
yukicoder

結果

テストケース

ソースコード
