結果
| 問題 | No.2712 Play more! |
| ユーザー |
 VvyLw
|
| 提出日時 | 2024-04-02 16:37:37 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 46,454 bytes |
| コンパイル時間 | 5,153 ms |
| コンパイル使用メモリ | 295,456 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-30 23:14:49 |
| 合計ジャッジ時間 | 7,222 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 1 ms
6,820 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | WA | - |
| testcase_05 | AC | 2 ms
6,820 KB |
| testcase_06 | AC | 2 ms
6,820 KB |
| testcase_07 | AC | 74 ms
6,824 KB |
| testcase_08 | AC | 75 ms
6,816 KB |
| testcase_09 | AC | 74 ms
6,820 KB |
| testcase_10 | WA | - |
| testcase_11 | AC | 35 ms
6,816 KB |
| testcase_12 | AC | 168 ms
6,824 KB |
| testcase_13 | AC | 23 ms
6,816 KB |
| testcase_14 | AC | 100 ms
6,820 KB |
| testcase_15 | AC | 174 ms
6,816 KB |
| testcase_16 | AC | 11 ms
6,820 KB |
| testcase_17 | AC | 4 ms
6,820 KB |
| testcase_18 | AC | 23 ms
6,816 KB |
| testcase_19 | AC | 6 ms
6,820 KB |
| testcase_20 | AC | 36 ms
6,824 KB |
| testcase_21 | AC | 15 ms
6,820 KB |
| testcase_22 | AC | 167 ms
6,816 KB |
| testcase_23 | AC | 6 ms
6,820 KB |
| testcase_24 | AC | 18 ms
6,816 KB |
| testcase_25 | AC | 4 ms
6,824 KB |
| testcase_26 | AC | 24 ms
6,816 KB |
| testcase_27 | AC | 36 ms
6,820 KB |
| testcase_28 | AC | 56 ms
6,816 KB |
| testcase_29 | AC | 20 ms
6,820 KB |
| testcase_30 | AC | 175 ms
6,816 KB |
| testcase_31 | AC | 56 ms
6,820 KB |
| testcase_32 | AC | 47 ms
6,816 KB |
| testcase_33 | AC | 2 ms
6,816 KB |
| testcase_34 | AC | 2 ms
6,820 KB |
| testcase_35 | AC | 2 ms
6,816 KB |
ソースコード
#line 1 "main.cpp"
/*#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")//*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#line 2 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
#ifndef TEMPLATE
#define TEMPLATE
#endif
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wdeprecated-copy"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
namespace VvyLw {
inline void wa_haya_exe() noexcept { std::cin.tie(nullptr) -> sync_with_stdio(false); }
void solve();
} // VvyLw
namespace zia_qu {
inline bool isdigit(const std::string &s);
}
std::mt19937 EhaL(std::hash<std::string>()("Huitloxopetl"));
std::mt19937 Random() {
std::random_device seed_gen;
std::mt19937 engine {seed_gen()};
return engine;
}
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/timer.hpp"
#line 5 "/home/wa_haya_exe/CP_Library/C++/core/timer.hpp"
using Timer = std::chrono::system_clock::time_point;
[[maybe_unused]] Timer start, stop;
#if local
void now(Timer &t){ t = std::chrono::system_clock::now(); }
void time(const Timer &t1, const Timer &t2){ std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << "ms\n"; }
#else
[[maybe_unused]] void now(Timer &t){ void(0); }
[[maybe_unused]] void time(const Timer &t1, const Timer &t2){ void(0); }
#endif
/**
* @brief タイマー
*/
#line 26 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0; i<(n); ++i)
#define rep2(i,n) for(ll i=0; i<(n); ++i)
#define rep3(i,a,b) for(ll i=(a); i<=(b); ++i)
#define rep4(i,a,b,c) for(ll i=(a); i<=(b); i+=(c))
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rvp1(n) for(ll i=(n); --i>=0;)
#define rvp2(i,n) for(ll i=(n); --i>=0;)
#define rvp3(i,a,b) for(ll i=(a); i>=(b); i--)
#define rvp4(i,a,b,c) for(ll i=(a); i>=(b); i-=(c))
#define rvp(...) overload4(__VA_ARGS__,rvp4,rvp3,rvp2,rvp1)(__VA_ARGS__)
#define all1(v) v.begin(),v.end()
#define all2(v,a) v.begin(),v.begin()+a
#define all3(v,a,b) v.begin()+a,v.begin()+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(v) v.rbegin(),v.rend()
#define rall2(v,a) v.rbegin(),v.rbegin()+a
#define rall3(v,a,b) v.rbegin()+a,v.rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define each1(elem,v) for(auto &elem: v)
#define each2(x,y,v) for(auto &[x,y]: v)
#define each3(x,y,z,v) for(auto &[x,y,z]: v)
#define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__)
#define sqrp1(n) for(ll i=0; i*i<(n); ++i)
#define sqrp2(i,n) for(ll i=0; i*i<(n); ++i)
#define sqrp3(i,a,b) for(ll i=(a); i*i<=(b); ++i)
#define sqrp(...) overload3(__VA_ARGS__,sqrp3,sqrp2,sqrp1)(__VA_ARGS__)
using ll = long long;
using ld = long double;
using uint = unsigned;
using ul = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/mypair.hpp"
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/constance.hpp"
#line 4 "/home/wa_haya_exe/CP_Library/C++/core/constance.hpp"
#ifndef TEMPLATE
using ll = long long;
using ld = long double;
#endif
template <class T> using L = std::numeric_limits<T>;
constexpr int dx[] = {0, 0, 0, -1, 1, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, -1, 1, -1, 1};
constexpr int MOD = 0x3b800001;
constexpr int M0D = 1e9 + 7;
constexpr int INF = 1 << 30;
constexpr ll LINF = (1LL << 61) - 1;
constexpr ld DINF = L<ld>::infinity();
template <class T> constexpr T LIM = L<T>::max();
#if __cplusplus >= 202100L
#include <numbers>
constexpr ld PI = std::numbers::pi;
constexpr ld E = std::numbers::e;
#else
#include <cmath>
const ld PI = std::acos(-1);
const ld E = 2.718281828459045;
#endif
/**
* @brief 定数
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/myvector.hpp"
#line 4 "/home/wa_haya_exe/CP_Library/C++/core/myvector.hpp"
#ifndef TEMPLATE
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
#endif
namespace vectors {
template <class T> using V = std::vector<T>;
using vi = V<ll>;
using vu = V<ul>;
using vd = V<ld>;
using vc = V<char>;
using vs = V<std::string>;
using vb = V<bool>;
using wi = V<vi>;
using wu = V<vu>;
using wd = V<vd>;
using wc = V<vc>;
using ws = V<vs>;
using wb = V<vb>;
template <class T, class U> inline V<U> ndiv(T&& n, U&& v) noexcept {
return V<U>(std::forward<T>(n), std::forward<U>(v));
}
template <class T, class... Ts> inline decltype(auto) ndiv(T&& n, Ts&&... v) noexcept {
return V<decltype(ndiv(std::forward<Ts>(v)...))>(std::forward<T>(n), ndiv(std::forward<Ts>(v)...));
}
template <class T> constexpr V<T>& operator++(V<T>& v) noexcept { for(auto &el: v) el++; return v; }
template <class T> constexpr V<T>& operator--(V<T>& v) noexcept { for(auto &el: v) el--; return v; }
template <class T, class U> constexpr V<T>& operator+=(V<T>& v, const U x) noexcept { for(auto &el: v) el+=x; return v; }
template <class T, class U> constexpr V<T>& operator-=(V<T>& v, const U x) noexcept { for(auto &el: v) el-=x; return v; }
template <class T, class U> constexpr V<T>& operator*=(V<T>& v, const U x) noexcept { for(auto &el: v) el*=x; return v; }
template <class T, class U> constexpr V<T>& operator/=(V<T>& v, const U x) noexcept { for(auto &el: v) el/=x; return v; }
template <class T, class U> constexpr V<T>& operator%=(V<T>& v, const U x) noexcept { for(auto &el: v) el%=x; return v; }
template <class T, class U> constexpr V<T> operator+(const V<T>& v, const U x) noexcept { V<T> res = v; res+=x; return res; }
template <class T, class U> constexpr V<T> operator-(const V<T>& v, const U x) noexcept { V<T> res = v; res-=x; return res; }
template <class T, class U> constexpr V<T> operator*(const V<T>& v, const U x) noexcept { V<T> res = v; res*=x; return res; }
template <class T, class U> constexpr V<T> operator/(const V<T>& v, const U x) noexcept { V<T> res = v; res/=x; return res; }
template <class T, class U> constexpr V<T> operator%(const V<T>& v, const U x) noexcept { V<T> res = v; res%=x; return res; }
} // vectors
#line 10 "/home/wa_haya_exe/CP_Library/C++/core/mypair.hpp"
namespace pairs {
template <class T, class U> using P = std::pair<T, U>;
template <class T> using PP = P<T,T>;
using pi = PP<ll>;
using pd = PP<ld>;
using pc = PP<char>;
using ps = PP<std::string>;
template <class T> constexpr PP<T> operator+(const PP<T>& a, const PP<T>& b) noexcept { return {a.first + b.first, a.second + b.second}; }
template <class T> constexpr PP<T> operator-(const PP<T>& a, const PP<T>& b) noexcept { return {a.first - b.first, a.second - b.second}; }
template <class T> constexpr PP<T> operator-(const PP<T>& a) noexcept { return {-a.first, -a.second}; }
template <class T, class U> constexpr PP<T> operator*(const PP<T>& a, const U& b) noexcept { return {a.first * b, a.second * b}; }
template <class T, class U> constexpr PP<T> operator/(const PP<T>& a, const U& b) noexcept { return {a.first / b, a.second / b}; }
template <class T> constexpr PP<T>& operator+=(PP<T>& a, const PP<T>& b) noexcept { return a = a + b; }
template <class T> constexpr PP<T>& operator-=(PP<T>& a, const PP<T>& b) noexcept { return a = a - b; }
template <class T, class U> constexpr PP<T>& operator*=(PP<T>& a, const U& b) noexcept { return a = a * b; }
template <class T, class U> PP<T>& operator/=(PP<T>& a, const U& b) noexcept { return a = a / b; }
template <class T> constexpr bool operator==(const PP<T> &p, const PP<T> &q) noexcept { return p.first==q.first && p.second==q.second; }
template <class T> constexpr bool operator!=(const PP<T> &p, const PP<T> &q) noexcept { return !(p==q); }
template <class T> constexpr bool operator<(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second<q.second; return p.first<q.first; }
template <class T> constexpr bool operator<=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first<q.first; }
template <class T> constexpr bool operator>(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; }
template <class T> constexpr bool operator>=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; }
template <class T, class U> constexpr bool operator==(const P<T,U> &p, const P<T,U> &q) noexcept { return p.first==q.first && p.second==q.second; }
template <class T, class U> constexpr bool operator!=(const P<T,U> &p, const P<T,U> &q) noexcept { return !(p==q); }
template <class T, class U> constexpr bool operator<(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second<q.second; return p.first<q.first; }
template <class T, class U> constexpr bool operator<=(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first<q.first; }
template <class T, class U> constexpr bool operator>(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; }
template <class T, class U> constexpr bool operator>=(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; }
template <class T> inline PP<T> rotate(const PP<T>& a){ return {-a.second, a.first}; } // 90 degree ccw
template <class T> inline pd rotate(const PP<T>& a, const int ang) {
assert(0<=ang && ang<360);
const ld rad=PI*ang/180;
return {a.first*std::cos(rad)-a.second*std::sin(rad), a.first*std::sin(rad)+a.second*std::cos(rad)};
}
template <class T> inline T dot(const PP<T>& a, const PP<T>& b){ return a.first * b.first + a.second * b.second; }
template <class T> inline T cross(const PP<T>& a, const PP<T>& b){ return dot(rotate(a), b); }
template <class T> inline T square(const PP<T>& a){ return dot(a, a); }
template <class T> inline ld grad(const PP<T>& a){ assert(a.first); return 1.0L * a.second / a.first; }
template <class T> inline ld abs(const PP<T>& a){ return std::hypotl(a.first, a.second); }
template <class T> inline T lcm(const PP<T>& a){ return std::lcm(a.first, a.second); }
template <class T> inline T gcd(const PP<T>& a){ return std::gcd(a.first, a.second); }
template <class T> inline PP<T> extgcd(const PP<T> &p) {
T x=1,y=0,t1=0,t2=0,t3=1,a,b;
std::tie(a,b)=p;
while(b) {
t1=a/b,a-=t1*b;
std::swap(a,b);
x-=t1*t2;
std::swap(x,t2);
y-=t1*t3;
std::swap(y,t3);
}
return {x,y};
}
template <class T> inline PP<T> normalize(PP<T> a) {
if(a == PP<T>{}) return a;
a /= gcd(a);
if(a < PP<T>{}) a = -a;
return a;
}
template <class T, class U> inline P<U,T> swap(const P<T,U> &p){ P<U,T> ret={p.second,p.first}; return ret; }
template <class T, class U> inline vectors::V<P<U,T>> swap(const vectors::V<P<T,U>> &vp) {
vectors::V<P<U,T>> ret;
for(const auto &el: vp) ret.emplace_back(swap(el));
return ret;
}
template <class T, class U> inline vectors::V<T> first(const vectors::V<P<T,U>> &vp) {
vectors::V<T> res;
for(const auto &el: vp) res.emplace_back(el.first);
return res;
}
template <class T, class U> inline vectors::V<U> second(const vectors::V<P<T,U>> &vp) {
vectors::V<U> res;
for(const auto &el: vp) res.emplace_back(el.second);
return res;
}
} // pairs
#line 64 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
using namespace vectors;
using namespace pairs;
template <size_t N> using ti = std::array<ll, N>;
using tri = ti<3>;
template <class T> using pq = std::priority_queue<T>;
template <class T> using pqr = std::priority_queue<T,V<T>,std::greater<T>>;
template <class T> using Tree = __gnu_pbds::tree<T,__gnu_pbds::null_type,std::less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template <class T> using TREE = __gnu_pbds::tree<T,__gnu_pbds::null_type,std::greater<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template <class T, class U> inline bool chmax(T& a, const U& b){ if(a<b){ a=b; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& a, const U& b){ if(a>b){ a=b; return 1; } return 0; }
template <class T, class U> inline bool overflow_if_add(const T a, const U b){ return (LIM<T>-a)<b; }
template <class T, class U> inline bool overflow_if_mul(const T a, const U b){ return (LIM<T>/a)<b; }
inline void fix(const short x){ std::cout << std::fixed << std::setprecision(x); }
inline void alpha(){ std::cout << std::boolalpha; }
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/io/input.hpp"
#line 7 "/home/wa_haya_exe/CP_Library/C++/core/io/input.hpp"
#ifndef TEMPLATE
typedef unsigned long long ul;
typedef __int128_t i128;
namespace zia_qu {
inline bool isdigit(const char c){ return std::isdigit(c); }
inline bool isdigit(const std::string &s){ bool ok=1, neg=s.front()=='-'; for(const auto &el: s){ if(neg){ neg=0; continue; } ok&=isdigit(el); } return ok; }
}
#endif
namespace IO {
template <class T, class U> std::istream& operator>>(std::istream &is, pairs::P<T, U> &p){ is >> p.first >> p.second; return is; }
template <class T, size_t N> std::istream& operator>>(std::istream &is, std::array<T, N> &a){ for(auto &el: a) is >> el; return is; }
template <class T> std::istream& operator>>(std::istream &is, vectors::V<T> &v){ for(auto &el: v) is >> el; return is; }
template <class T> std::istream& operator>>(std::istream &is, std::deque<T> &dq){ for(auto &el: dq) is >> el; return is; }
template <class T> inline bool in(T& x){ std::cin >> x; return 1; }
template <class Head, class... Tail> inline bool in(Head& head, Tail&... tail){ in(head); in(tail...); return 1; }
inline i128 to_i128(const std::string &s) {
assert(zia_qu::isdigit(s));
bool neg=s.front()=='-';
i128 ret = 0;
for(const auto &el: s) {
if(neg) {
neg=0;
continue;
}
ret = 10 * ret + el - '0';
}
if(s.front()=='-') ret=-ret;
return ret;
}
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define UL(...) ul __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) std::string __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type,name,size) vectors::V<type> name(size); in(name)
#define WEC(type,name,h,w) vectors::V<vectors::V<type>> name(h,vectors::V<type>(w)); in(name)
} // IO
/**
* @brief 入力
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/io/output.hpp"
#line 9 "/home/wa_haya_exe/CP_Library/C++/core/io/output.hpp"
#ifndef TEMPLATE
using i128 = __int128_t;
using u128 = __uint128_t;
#endif
namespace IO {
std::ostream &operator<<(std::ostream &dest, const i128 &value) {
std::ostream::sentry s(dest);
if(s) {
u128 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;
}
template <class T, class U> std::ostream& operator<<(std::ostream &os, const std::pair<T, U> &p){ os << p.first << ' ' << p.second; return os; }
template <class T, size_t N> std::ostream& operator<<(std::ostream &os, const std::array<T, N> &a){ if(a.size()){ os << a.front(); for(auto i=a.begin(); ++i!=a.end();){ os << ' ' << *i; } } return os; }
template <class T> std::ostream& operator<<(std::ostream &os, const std::vector<T> &v){ if(v.size()){ os << v.front(); for(auto i=v.begin(); ++i!=v.end();){ os << ' ' << *i; } } return os; }
template <class K, class V> std::ostream& operator<<(std::ostream &os, const std::map<K, V> &m){ if(m.size()){ os << m.begin()->first << ' ' << m.begin()->second; for(auto i=m.begin(); ++i!=m.end();){ os << '\n' << i->first << ' ' << i->second; } } return os; }
template <class T> std::ostream& operator<<(std::ostream &os, const std::set<T> &st){ if(st.size()){ os << *st.begin(); for(auto i=st.begin(); ++i!=st.end();){ os << ' ' << *i; } } return os; }
template <class T> std::ostream& operator<<(std::ostream &os, const std::multiset<T> &ms){ if(ms.size()){ os << *ms.begin(); for(auto i=ms.begin(); ++i!=ms.end();){ os << ' ' << *i; } } return os; }
template <class T> std::ostream& operator<<(std::ostream &os, const std::deque<T> &dq){ if(dq.size()){ os << dq.front(); for(auto i=dq.begin(); ++i!=dq.end();){ os << ' ' << *i; } } return os; }
inline void out(){ std::cout << '\n'; }
template <bool flush=false, class T> inline void out(const T& x){ std::cout << x << '\n'; if(flush) std::cout.flush(); }
template <bool flush=false, class Head, class... Tail> inline void out(const Head& head, const Tail&... tail){ std::cout << head << ' '; out<flush>(tail...); }
template <bool flush=false, class T> inline void vout(const T& v){ std::cout << v << '\n'; if(flush) std::cout.flush(); }
template <bool flush=false, class T> inline void vout(const std::vector<T>& v){ for(const auto &el: v) std::cout << el << '\n'; if(flush) std::cout.flush(); }
template <bool flush=false, class Head, class... Tail> inline void vout(const Head& head, const Tail&... tail){ std::cout << head << '\n'; vout<flush>(tail...); }
#define fin(...) do{ out(__VA_ARGS__); return; }while(false)
} // IO
#if local
//https://gist.github.com/naskya/1e5e5cd269cfe16a76988378a60e2ca3
#include <C++/core/io/debug_print.hpp>
#else
#define dump(...) static_cast<void>(0)
#endif
/**
* @brief 出力
*/
#line 83 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
using namespace IO;
namespace zia_qu {
#define elif else if
#define eid(el,v) size_t(&el-&v[0])
#define bif(bit,tar) if(((bit)>>(tar))&1)
#define nxp(x) std::next_permutation(all(x))
#define prp(x) std::prev_permutation(all(x))
#define strpl(s,a,b) std::regex_replace(s,std::regex(a),b)
#define rgxsr(s,rgx) std::regex_search(s,std::regex(rgx))
inline void YES(const bool ok=1){ out(ok?"YES":"NO"); }
inline void NO(const bool ok=1){ YES(!ok); }
inline void Yes(const bool ok=1){ out(ok?"Yes":"No"); }
inline void No(const bool ok=1){ Yes(!ok); }
inline void yes(const bool ok=1){ out(ok?"yes":"no"); }
inline void no(const bool ok=1){ yes(!ok); }
template <class T> inline T sqr(const T x){ return x*x; }
template <class T> inline T cub(const T x){ return x*x*x; }
template <class T> inline T mod(T x, const T m) {
x %= m;
return x < 0 ? x + m : x;
}
template <class T> inline T pow(T a, T b, const T mod=0) {
T res=1;
if(mod) {
res%=mod;
a%=mod;
}
while(b>0) {
if(b&1) res*=a;
if(mod) res%=mod;
a*=a;
if(mod) a%=mod;
b>>=1;
}
return res;
}
inline ll ceil(const ld x, const ll m){ return std::ceil(x/m); }
inline ld round(const ld x, const ll m, const short fx=0){ if(!fx) return std::round(x/m); const ul y=pow<ul>(10,fx); return std::round((x*y)/m)/y; }
inline ld log(const ll x, const ld base=2){ return std::log2(x)/std::log2(base); }
inline int bitdigit(const ll x){ return 64-__builtin_clzll(x); }
inline int popcnt(const ll x){ return __builtin_popcountll(x); }
inline int fione(const ll x){ return __builtin_ffsll(x); }
inline int zrcnt(const ll x){ return __builtin_ctzll(x); }
template <class T=ll> inline bool scope(const T a, const T x, const T b){ return a <= x && x <= b; }
inline bool isupper(const char c){ return std::isupper(c); }
inline bool isupper(const std::string &s){ bool ok=1; each(el,s) ok&=isupper(el); return ok; }
inline bool islower(const char c){ return std::islower(c); }
inline bool islower(const std::string &s){ bool ok=1; each(el,s) ok&=islower(el); return ok; }
inline bool isalpha(const char c){ return std::isalpha(c); }
inline bool isalpha(const std::string &s){ bool ok=1; each(el,s) ok&=isalpha(el); return ok; }
inline bool isdigit(const char c){ return std::isdigit(c); }
inline bool isdigit(const std::string &s){ bool ok=1, neg=s.front()=='-'; each(el,s){ if(neg){ neg=0; continue; } ok&=isdigit(el); } return ok; }
inline bool isalnum(const char c){ return std::isalnum(c); }
inline bool isalnum(const std::string &s){ bool ok=1; each(el,s) ok&=isalnum(el); return ok; }
inline bool isspace(const char c){ return std::isspace(c); }
inline bool isspace(const std::string &s){ bool ok=1; each(el,s) ok&=isspace(el); return ok; }
inline bool ispunct(const char c){ return std::ispunct(c); }
inline bool ispunct(const std::string &s){ bool ok=1; each(el,s) ok&=ispunct(el); return ok; }
inline bool isprint(const char c){ return std::isprint(c); }
inline bool isprint(const std::string &s){ bool ok=1; each(el,s) ok&=isprint(el); return ok; }
inline ll strins(std::string &s, const int id, const std::string &t){ s.insert(id,t); return s.size(); }
inline std::string toupper(std::string s){ each(c,s) c=std::toupper(c); return s; }
inline std::string tolower(std::string s){ each(c,s) c=std::tolower(c); return s; }
inline vi ten_to_adic(ll n, const short base) {
if(n==0) {
return {0};
}
vi res;
while(n) {
res.emplace_back(n%base);
n/=base;
}
return res;
}
inline ll adic_to_ten(const vi &v, const short base) {
ll res=0;
each(el,v) {
res+=pow<ll>(base,eid(el,v))*el;
}
return res;
}
inline std::string to_hex(const ll x, const bool upper = false) {
std::stringstream ss;
ss << std::hex << x;
std::string s = ss.str();
if(upper) s=toupper(s);
return s;
}
inline std::string to_oct(const ll x) {
std::stringstream s;
s << std::oct <<x;
return s.str();
}
inline std::string to_bin(const ll x) {
std::stringstream ss;
ss<<std::bitset<64>(x);
std::string s=ss.str();
std::reverse(all(s));
s.resize(ten_to_adic(x,2).size());
std::reverse(all(s));
return s;
}
inline ll to_ten(const std::string &s, const short base){ return std::stoll(s,nullptr,base); }
template <class... Ts> constexpr ul sygcd(const Ts... a) noexcept { std::vector v=std::initializer_list<std::common_type_t<Ts...>>{a...}; ul g=0; each(el,v) g=std::gcd(g,el); return g; }
template <class... Ts> constexpr ul sylcm(const Ts... a) noexcept { std::vector v=std::initializer_list<std::common_type_t<Ts...>>{a...}; ul l=1; each(el,v) l=std::lcm(l,el); return l; }
template <class... Ts> constexpr auto symin(const Ts... a) noexcept { return std::min(std::initializer_list<std::common_type_t<Ts...>>{a...}); }
template <class... Ts> constexpr auto symax(const Ts... a) noexcept { return std::max(std::initializer_list<std::common_type_t<Ts...>>{a...}); }
template <class K, class U> inline V<K> kyl(const std::map<K,U> &m, const U val) {
V<K> keys;
for(auto it=m.cbegin(); it!=m.cend(); ++it) {
if(it->second==val) keys.emplace_back(it->first);
}
return keys;
}
template <class K, class V> inline K kymin(const std::map<K,V> &m){ return m.begin()->first; }
template <class K, class V> inline K kymax(const std::map<K,V> &m){ return m.rbegin()->first; }
template <class K, class V> inline V kymin_v(const std::map<K,V> &m){ return m.begin()->second; }
template <class K, class V> inline V kymax_v(const std::map<K,V> &m){ return m.rbegin()->second; }
template <class K, class V> inline V vlmin(const std::map<K,V> &m){
const auto pr = *std::min_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
return pr.second;
}
template <class K, class V> inline V vlmax(const std::map<K,V> &m){
const auto pr = *std::max_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
return pr.second;
}
template <class K, class V> inline K vlmin_k(const std::map<K,V> &m){
const auto pr = *std::min_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
return pr.first;
}
template <class K, class V> inline K vlmax_k(const std::map<K,V> &m){
const auto pr = *std::max_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
return pr.first;
}
} // zia qu
namespace Lady_sANDy {
template <class T> inline void rev(T& v){ std::reverse(all(v)); }
template <class T> inline void rev(T& v, const int a, const int b){ std::reverse(all(v,a,b+1)); }
template <class T> inline T revd(const T& v){ auto c=v; rev(c); return c; }
template <class T> inline T revd(const T& v, const int a, const int b){ auto c=v; rev(c,a,b); return c; }
template <class T> inline void Sort(T& v){ std::sort(all(v)); }
template <class T> inline void Sort(T& v, const int a, const int b){ std::sort(all(v,a,b+1)); }
template <class T> inline T sorted(const T& v){ auto c=v; Sort(c); return c; }
template <class T> inline T sorted(const T& v, const int a, const int b){ auto c=v; Sort(c,a,b); return c; }
template <class T> inline void Sortt(T& v){ std::sort(rall(v)); }
template <class T> inline void Sortt(T& v, const int a, const int b){ std::sort(rall(v,v.size()-b-1,v.size()-a)); }
template <class T> inline T Sorted(const T& v){ auto c=v; Sortt(c); return c; }
template <class T> inline T Sorted(const T& v, const int a, const int b){ auto c=v; Sortt(c,a,b); return c; }
template <class T> inline void Sorth(T& v){ std::make_heap(all(v)); std::sort_heap(all(v)); }
template <class T> inline T mrg(const T& a, const T& b){ T res; std::merge(all(a),all(b),std::back_inserter(res)); return res; }
template <class T> inline T Min(const V<T>& v){ return *std::min_element(all(v)); }
template <class T> inline T Min(const V<T>& v, const int a, const int b){ return *std::min_element(all(v,a,b+1)); }
template <class T> inline T Max(const V<T>& v){ return *std::max_element(all(v)); }
template <class T> inline T Max(const V<T>& v, const int a, const int b){ return *std::max_element(all(v,a,b+1)); }
template <class T> inline int Min_i(const T& v){ return std::min_element(all(v))-v.begin(); }
template <class T> inline int Max_i(const T& v){ return std::max_element(all(v))-v.begin(); }
template <class T, class U> inline int LB(const T& v, const U x){ return std::lower_bound(all(v),x)-v.begin(); }
template <class T, class U> inline int UB(const T& v, const U x){ return std::upper_bound(all(v),x)-v.begin(); }
template <class T, class U> inline bool BS(const T& v, const U x){ return std::binary_search(all(v),x); }
template <class T, class U, class Boolean=bool> inline bool BS(const T& v, const U x, const Boolean &fn){ return std::binary_search(all(v),x,fn); }
template <class T, class Boolean=bool> inline bool All(const T& v, const Boolean &fn){ return std::all_of(all(v),fn); }
template <class T, class Boolean=bool> inline bool Exist(const T& v, const Boolean &fn){ return std::any_of(all(v),fn); }
template <class T, class Boolean=bool> inline int pt(T& v, const Boolean &fn){ auto p=std::partition(all(v),fn); return p-v.begin(); }
template <class T, class Boolean=bool> inline int ptp(const T& v, const Boolean &fn){ return std::partition_point(all(v),fn)-v.begin(); }
template <class T, class U> inline int fnd(const T& v, const U x){ auto itr=std::find(all(v),x); return itr!=v.end()?itr-v.begin():-1; }
template <class T> inline int src(const T& s, const T& t){ auto itr=std::search(all(s),all(t)); return itr!=s.end()?itr-s.begin():-1; }
template <class T, class U> inline void rpl(T& v, const U fn, const U r){ std::replace(all(v),fn,r); }
template <class T, class U, class Boolean=bool> inline void rplif(T& v, const Boolean &fn, const U r){ std::replace_if(all(v),fn,r); }
template <class T, class Boolean=bool> inline ul cntif(const T& v, const Boolean &fn){ return std::count_if(all(v),fn); }
template <class T> inline T Count(V<T>& v, ll x){ if(!std::is_sorted(all(v))) Sort(v); return UB(v,x)-LB(v,x); }
template <class T> inline T IP(const V<T>& v, const V<T>& u, T init){ return std::inner_product(all(v),u.begin(),init); }
inline vi iot(int n, ll init=0){ vi a(n); std::iota(all(a),init); return a; }
template <class T, class U, class F> inline V<T> trans(const V<U>& v, const F &fn){ V<T> res; std::transform(all(v),std::back_inserter(res),fn); return res; }
template <class T, class U> inline int ers(T& v, const U x){ v.erase(std::remove(all(v),x),v.end()); return v.size(); }
template <class T, class Boolean=bool> int ersif(T& v, const Boolean &fn){ v.erase(std::remove_if(all(v),fn),v.end()); return v.size(); }
template <class T> inline int unq(T& v){ if(!std::is_sorted(all(v))) Sort(v); v.erase(unique(all(v)),v.end()); return v.size(); }
template <class T> inline T cp(const T& v){ T res; copy(all(v),back_inserter(res)); return res; }
template <class T> inline T cp(const T& v, const int a, const int b){ T res; std::copy(all(v,a,b),std::back_inserter(res)); return res; }
template <class T> inline void rtt(T& s, const int idx){ const int id=zia_qu::mod<int>(idx,s.size()); std::rotate(all(s,id),s.end()); }
template <class T> inline void rtt(T& s, const int a, const int b, const int c){ std::rotate(all(s,a,b),s.end()-c); }
template <class T> inline T setdif(const T& s, const T& t){ assert(std::is_sorted(all(s))&&std::is_sorted(all(t))); T res; std::set_difference(all(s),all(t),std::inserter(res,std::end(res))); return res; }
template <class T> inline T setsum(const T& s, const T& t){ assert(std::is_sorted(all(s))&&std::is_sorted(all(t))); T res; std::set_union(all(s),all(t),std::inserter(res,std::end(res))); return res; }
template <class T> inline T setmul(const T& s, const T& t){ assert(std::is_sorted(all(s))&&std::is_sorted(all(t))); T res; std::set_intersection(all(s),all(t),std::inserter(res,std::end(res))); return res; }
template <class T> inline V<T> adf(const V<T>& v){ V<T> a; std::adjacent_difference(all(v),std::back_inserter(a)); rtt(a,1); a.pop_back(); return a; }
template <class T, class F> inline V<T> isum(const V<T> &v, const F &fn){ V<T> s{0}; std::inclusive_scan(all(v),std::back_inserter(s),fn); return s; }
template <class T> inline V<T> rext(const V<T>& v, const int size){ V<T> res; std::sample(all(v),std::back_inserter(res),size,Random()); return res; }
template <class T> inline T rext(const V<T>& v){ V<T> res; std::sample(all(v),std::back_inserter(res),1,Random()); return res.front(); }
template <class T> inline ll vsum(const T &v){ return std::accumulate(all(v),0LL); }
template <class T> inline ll vsum(const T &v, ll a, ll b){ return std::accumulate(all(v,a,b),0LL); }
template <class T> inline ld vdsum(const T &v){ return std::accumulate(all(v),0.0L); }
template <class T> inline ld vdsum(const T &v, ll a, ll b){ return std::accumulate(all(v,a,b),0.0L); }
template <class T> inline ll vmul(const T &v){ return std::accumulate(all(v),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ll vmul(const T &v, ll a, ll b){ return std::accumulate(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(const T &v){ return std::accumulate(all(v),1.0L,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(const T &v, ll a, ll b){ return std::accumulate(all(v,a,b),1.0L,[](ll acc,ll i){ return acc*i; }); }
} // Lady s&y
#line 2 "/home/wa_haya_exe/CP_Library/C++/math/divisor.hpp"
#line 5 "/home/wa_haya_exe/CP_Library/C++/math/divisor.hpp"
namespace Heileden {
template <class T> inline std::vector<T> div(const T n) {
std::vector<T> d;
for(int64_t i = 1; i * i <= n; ++i) {
if(n % i == 0) {
d.emplace_back(i);
if(i * i != n) {
d.emplace_back(n / i);
}
}
}
std::ranges::sort(d);
return d;
}
}
/**
* @brief 約数列挙
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/math/primefactor.hpp"
#line 5 "/home/wa_haya_exe/CP_Library/C++/math/primefactor.hpp"
namespace Heileden {
template <class T> inline std::vector<std::pair<T, int>> prmfct(T n) {
std::vector<std::pair<T, int>> res;
for(int64_t i = 2; i * i <= n; ++i) {
if(n % i != 0) {
continue;
}
int tmp = 0;
while(n % i == 0) {
tmp++;
n /= i;
}
res.emplace_back(i, tmp);
}
if(n != 1) {
res.emplace_back(n, 1);
}
return res;
}
}
/**
* @brief 素因数分解
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/math/primetable.hpp"
#line 4 "/home/wa_haya_exe/CP_Library/C++/math/primetable.hpp"
namespace Heileden {
struct p_table {
std::vector<int> SoE;
p_table(const int n): SoE(n + 1, 1) {
SoE[0] = SoE[1] = 0;
for(int64_t i = 2; i <= n; ++i) {
if(!SoE[i]) {
continue;
}
for(int64_t j = i * i; j <= n; j += i) {
SoE[j] = 0;
}
}
}
std::vector<int> get() {
std::vector<int> p;
for(size_t i = 2; i < SoE.size(); ++i) {
if(SoE[i]) {
p.emplace_back(i);
}
}
return p;
}
};
}
/**
* @brief Sieve of Eratosthenes
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/math/primefactortable.hpp"
#line 6 "/home/wa_haya_exe/CP_Library/C++/math/primefactortable.hpp"
namespace Heileden {
struct p_fact {
std::vector<int64_t> spf;
p_fact(const int n): spf(n + 1){
std::iota(spf.begin(), spf.end(), 0);
for(int64_t i = 2; i * i <= n; ++i) {
if(spf[i] == i) {
for(int64_t j = i * i; j <= n; j += i) {
if(spf[j]==j) {
spf[j]=i;
}
}
}
}
}
std::map<int, int> get(int n) {
std::map<int, int> m;
while(n != 1) {
m[spf[n]]++;
n /= spf[n];
}
return m;
}
};
}
/**
* @brief 素因数分解テーブル
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/math/psum/psum.hpp"
#line 6 "/home/wa_haya_exe/CP_Library/C++/math/psum/psum.hpp"
namespace Heileden {
struct psum {
private:
int n;
bool not_built;
vectors::vi s;
public:
psum(const vectors::vi& v): s{0} { std::partial_sum(v.cbegin(), v.cend(), std::back_inserter(s)); }
psum(const int n): n(n), not_built(true), s(n + 1){}
vectors::vi get() const { return s; }
// [l, r]
ll sum(const int l, const int r) const { return s[r] - s[l]; }
void add(const int l, const int r, const ll x) {
assert(not_built);
s[l] += x;
s[r] -= x;
}
vectors::vi build() {
assert(not_built);
vectors::vi res;
std::partial_sum(s.cbegin(), s.cend(), std::back_inserter(res));
not_built = false;
res.resize(n);
return res;
}
};
}
/**
* @brief 累積和
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/math/kthrooti.hpp"
#line 4 "/home/wa_haya_exe/CP_Library/C++/math/kthrooti.hpp"
#ifndef TEMPLATE
typedef unsigned long long ul;
template <class T, class U> inline bool overflow_if_mul(const T a, const U b){ return (std::numeric_limits<T>::max()/a)<b; }
#endif
namespace Heileden {
inline ul kthrooti(const ul n, const int k) {
if(k==1) {
return n;
}
const auto chk=[&](const unsigned x) {
ul mul=1;
for(int i = 0; i < k; ++i) {
if(overflow_if_mul(mul, x)) {
return false;
}
mul*=x;
}
return mul<=n;
};
ul ret=0;
for(int i = 32; --i >= 0;) {
if(chk(ret|(1U<<i))) {
ret|=1U<<i;
}
}
return ret;
}
}
/**
* @brief k乗根(整数)
*/
#line 289 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
namespace Heileden {
template <class T, class Boolean=bool> inline T bins(T ok, T ng, const Boolean &fn, const ld eps = 1) {
while(std::abs(ok-ng)>eps) {
T mid=(ok+ng)/2;
(fn(mid)?ok:ng) = mid;
}
return ok;
}
template <class T> inline V<T> press(const V<T>& v) {
V<T> res,cp=v;
Lady_sANDy::unq(cp);
each(el,v) res.emplace_back(Lady_sANDy::LB(cp,el));
return res;
}
template <class T> inline V<T> press(V<T> &c1, V<T> &c2) {
V<T> res;
const int n = c1.size();
rep(n) {
for(T d = 0; d < 1; d++) {
T tc1 = c1[i]+d;
T tc2 = c2[i]+d;
res.emplace_back(tc1);
res.emplace_back(tc2);
}
}
Lady_sANDy::unq(res);
rep(n) {
c1[i]=Lady_sANDy::LB(res,c1[i]);
c2[i]=Lady_sANDy::LB(res,c2[i]);
}
return res;
}
inline vs rtt(const vs &s) {
const int h=s.size(), w=s.front().size();
vs t(w,std::string(h,{}));
rep(h) rep(j,w) t[j][i]=s[i][j];
rep(w) Lady_sANDy::rev(t[i]);
return t;
}
template <class T> inline V<V<T>> rtt(const V<V<T>>& v) {
const int h=v.size(), w=v.front().size();
V<V<T>> res(w,V<T>(h));
rep(h) rep(j,w) res[j][i]=v[i][j];
rep(w) Lady_sANDy::rev(res[i]);
return res;
}
template <class T> inline T factor(T n, const T mod=0) {
T res=1;
while(n>0) {
res*=n--;
if(mod) res%=mod;
}
return res;
}
template <class T=ll> inline T perm(T n, const T r, const T mod=0) {
const T tmp=n;
T res=1;
while(n>tmp-r) {
res*=n--;
if(mod) res%=mod;
}
return res;
}
template <class T=ll> inline T binom(T n, const T r, const T mod=0) {
if(r < 0 || n < r) return 0;
T res = 1;
rep(i,1,r) {
res*=n--;
if(mod) res%=mod;
res/=i;
if(mod) res%=mod;
}
return res;
}
inline bool is_prime(const ul n) {
if(n==1) return 0;
sqrp(i,2,n) if(n%i==0) return 0;
return 1;
}
inline bool is_int(const ld n){ return n == std::floor(n); }
inline bool is_sqr(const ll n){ return is_int(std::sqrt(n)); }
} // Heileden
/**
* @brief テンプレート
* @docs docs/template.md
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/graph/WeightedGraph.hpp"
#line 2 "/home/wa_haya_exe/CP_Library/C++/graph/Graph.hpp"
#line 8 "/home/wa_haya_exe/CP_Library/C++/graph/Graph.hpp"
#ifndef TEMPLATE
template <class T, class U> bool chmin(T& a, const U& b){ if(a>b){ a=b; return 1; } return 0; }
#endif
#line 2 "/home/wa_haya_exe/CP_Library/C++/graph/edge.hpp"
struct edge {
int src, to, id;
long long cost;
edge(){}
edge(const int src_, const int to_, const int id_ = -1, const long long cost_ = 0): src(src_), to(to_), id(id_), cost(cost_){}
operator int() const { return to; }
};
/**
* @brief Edge
*/
#line 12 "/home/wa_haya_exe/CP_Library/C++/graph/Graph.hpp"
template <bool undirected = true> struct graph: std::vector<std::vector<edge>> {
protected:
int indexed, id;
std::vector<edge> edges;
public:
graph(){}
graph(const int n, const int indexed_ = 1): indexed(indexed_), id(0){ this -> resize(n); }
void add(int a, int b) {
a -= indexed, b-= indexed;
(*this)[a].emplace_back(a, b, id);
edges.emplace_back(a, b, id++);
if(undirected) {
(*this)[b].emplace_back(b, a, --id);
edges.emplace_back(b, a, id++);
}
}
void input(const int m) {
for(int i = 0; i < m; ++i) {
int a, b;
std::cin >> a >> b;
add(a, b);
}
}
std::vector<int> all_dist(const int v) {
std::vector<int> d(this -> size(), -1);
std::queue<int> q;
d[v] = 0;
q.emplace(v);
while(q.size()) {
const int tmp = q.front();
q.pop();
for(const auto &el: (*this)[tmp]) {
if(d[el] != -1) {
continue;
}
d[el] = d[tmp] + 1;
q.emplace(el);
}
}
return d;
}
int dist(const int u, const int v) const { return all_dist(u)[v]; }
std::vector<int> t_sort() {
const int n = this -> size();
std::vector<int> deg(n);
for(int i = 0; i < n; ++i) {
for(const auto ed: (*this)[i]) {
deg[ed]++;
}
}
std::stack<int> sk;
for(int i = 0; i < n; ++i) {
if(deg[i] == 0) {
sk.emplace(i);
}
}
std::vector<int> ord;
while(sk.size()) {
const auto tmp = sk.top();
sk.pop();
ord.emplace_back(tmp);
for(const auto ed: (*this)[tmp]) {
if(--deg[ed] == 0) {
sk.emplace(ed);
}
}
}
return ord.size() == size() ? ord : std::vector<int>{};
}
std::vector<edge> cycle() {
const int n = size();
std::vector<int> used(n);
std::vector<edge> pre(n), cycle;
const auto dfs = [&](const auto &f, const int i) -> bool {
used[i] = 1;
for(const auto &e: (*this)[i]) {
if(used[e] == 0) {
pre[e] = e;
if(f(f, e)) {
return true;
}
} else if(used[e] == 1) {
int now = i;
while(now != e) {
cycle.emplace_back(pre[now]);
now = pre[now].src;
}
cycle.emplace_back(e);
return true;
}
}
used[i] = 2;
return false;
};
for(int i = 0; i < n; ++i) {
if(used[i] == 0 && dfs(dfs, i)) {
std::reverse(cycle.begin(), cycle.end());
return cycle;
}
}
return {};
}
};
typedef std::vector<edge> ve;
typedef std::vector<ve> we;
/**
* @brief グラフライブラリ
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/graph/ShortestPath.hpp"
#pragma GCC diagnostic ignored "-Wreorder"
#line 7 "/home/wa_haya_exe/CP_Library/C++/graph/ShortestPath.hpp"
struct ShortestPath {
private:
const std::vector<long long> cost;
const std::vector<int> src;
public:
ShortestPath(const std::vector<long long> &cost, const std::vector<int> &src): cost(cost), src(src){}
bool is_thru(const int i){ return src[i] != -1; }
std::vector<int> path(int i) {
std::vector<int> res;
for(; i != -1; i = src[i]) {
res.emplace_back(i);
}
std::ranges::reverse(res);
return res;
}
std::vector<long long> get() const { return cost; }
};
/**
* @brief 最短路
*/
#line 5 "/home/wa_haya_exe/CP_Library/C++/graph/WeightedGraph.hpp"
template <bool undirected = true> struct w_graph: graph<undirected> {
private:
using graph<undirected>::indexed;
using graph<undirected>::id;
using graph<undirected>::edges;
public:
w_graph(const int n, const int indexed_ = 1): graph<undirected>(n, indexed_){}
using graph<undirected>::all_dist;
using graph<undirected>::dist;
using graph<undirected>::t_sort;
using graph<undirected>::cycle;
void add(int a, int b, const long long cost) {
a -= indexed, b -= indexed;
(*this)[a].emplace_back(a, b, id, cost);
edges.emplace_back(a, b, id++, cost);
if(undirected) {
(*this)[b].emplace_back(b, a, --id, cost);
edges.emplace_back(b, a, id++, cost);
}
}
void input(const int m) {
for(int i = 0; i < m; ++i) {
int a, b;
long long c;
std::cin >> a >> b >> c;
add(a, b, c);
}
}
ShortestPath dijkstra(const int v) {
std::vector<long long> cst(this -> size(), (1LL << 61) - 1);
std::vector<int> src(this -> size(), -1);
std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> dj;
cst[v] = 0;
dj.emplace(cst[v], v);
while(dj.size()) {
const auto tmp = dj.top();
dj.pop();
if(cst[tmp.second] < tmp.first) {
continue;
}
for(const auto &el: (*this)[tmp.second]) {
if(chmin(cst[el], tmp.first + el.cost)) {
src[el] = tmp.second;
dj.emplace(cst[el], el);
}
}
}
return {cst, src};
}
std::vector<long long> bellman_ford(const int v) {
const int n = this -> size();
std::vector<long long> dist(n, INT64_MAX);
dist[v] = 0;
for(int i = 0; i < n - 1; ++i) {
for(auto &e: edges) {
if(dist[e.src] == INT64_MAX) {
continue;
}
chmin(dist[e], dist[e.src] + e.cost);
}
}
for(const auto &e: edges) {
if(dist[e.src] == INT64_MAX) {
continue;
}
if(dist[e.src] + e.cost < dist[e]) {
return std::vector<long long>();
}
}
return dist;
}
std::vector<long long> spfa(const int v) {
const int n = this -> size();
std::vector<long long> cst(n, INT64_MAX);
std::vector<int> pending(n), times(n);
std::queue<int> q;
q.emplace(v);
pending[v] = 1;
++times[v];
cst[v] = 0;
while(!q.empty()) {
const int p = q.front();
q.pop();
pending[p] = 0;
for(const auto &e : (*this)[p]) {
const long long next = cst[p] + e.cost;
if(next >= cst[e]) {
continue;
}
cst[e] = next;
if(!pending[e]) {
if(++times[e] >= n) {
return std::vector<long long>();
}
pending[e] = 1;
q.emplace(e);
}
}
}
return cst;
}
std::vector<std::vector<long long>> warshall_floyd() {
const int n = this -> size();
const long long lim = (1LL << 61) - 1;
std::vector cst(n, std::vector(n, lim));
for(int i = 0; i < n; ++i) {
cst[i][i] = 0;
}
for(int i = 0; i < n; ++i) {
for(const auto &j: (*this)[i]) {
cst[i][j] = j.cost;
}
}
for(int k = 0; k < n; ++k) {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(cst[i][k] == lim || cst[k][j] == lim) {
continue;
}
chmin(cst[i][j], cst[i][k] + cst[k][j]);
}
}
}
return cst;
}
};
/**
* @brief 重み付きグラフライブラリ
*/
#line 6 "main.cpp"
using namespace std;
using namespace zia_qu;
using namespace Lady_sANDy;
using namespace Heileden;
int main() {
VvyLw::wa_haya_exe();
now(start);
int T=1;
//in(T);
while(T--) VvyLw::solve();
now(stop);
time(start, stop);
}
// --------------------------------------------------------------------------------------------------------------
void VvyLw::solve() {
INT(n,m);
VEC(int,a,n);
w_graph<false> g(2*n);
rep(i,1,n) {
g.add(i,i+n,-a[i-1]);
}
while(m--) {
INT(u,v,c);
g.add(u+n,v,c);
}
const auto bf=g.bellman_ford(0);
dump(bf);
if(bf.empty()) {
out("inf");
} else {
out(-bf[2*n-1]);
}
}