/* #include void self::main(){ LL(N,M,Q); VL(N,a); VV(M,u,v,w);dec(u,v); DsuPlain uf(N); fo(i,M){ if(w[i]==0)uf.merge(u[i],v[i]); } auto group=uf.groups(); ll C=group.size(); vecgid(N); fo(k,C)fe(group[k],i)gid[i]=k; Graphg(C); fo(i,M){ if(uf.same(u[i],v[i]))continue; if(i>=61)continue; g.add_edge(gid[u[i]],gid[v[i]],w[i]*pow2(i+1)); g.add_edge(gid[v[i]],gid[u[i]],w[i]*pow2(i+1)); } vecwarp(C,oo); fo(i,N)amin(warp[gid[i]],a[i]); FO(Q){ LL(s,t);dec(s,t); mapdp; dp[gid[s]]=0; min_heap>q; q.emplace(0,gid[s]); while(q.size()){ auto[du,u]=q.pop(); if(dp[u]ep; ep[gid[t]]=0; min_heap>{}.swap(q); q.emplace(0,gid[t]); while(q.size()){ auto[du,u]=q.pop(); if(ep[u] using namespace std; namespace self{void main();void sub();void pp(auto&&...a);void ppe(auto&&...a);} int main(){cin.tie(nullptr)->sync_with_stdio(0);cout<__VA_ARGS__;fe(refs(__VA_ARGS__),e)e.get().resizes(n);lin(__VA_ARGS__) #define RDVV(T,n,...) vec__VA_ARGS__;fe(refs(__VA_ARGS__),e)e.get().resizes(n);vin(__VA_ARGS__) #define VL(n,...) RDVL(ll,n,__VA_ARGS__) #define VV(n,...) RDVV(ll,n,__VA_ARGS__) #define FO(n) for(ll IJK=n;IJK-->0;) #define fo(i,...) for(auto[i,i##stop,i##step]=for_range(0,__VA_ARGS__);iconstexpr auto for_range(T s,T b){T a=0;if(s)swap(a,b);return array{a-s,b,1-s*2};} void lin(auto&...a){(cin>>...>>a);} void vin(auto&...a){fo(i,(a.size()&...))(cin>>...>>a[i]);} constexpr ll size10(auto x){x|=1;ll r=0;while(x>0)x/=10,++r;return r;} templateconstexpr ll maxsize10(){return size10(numeric_limits::max());} templateT pow2(ll n){return T(1)<struct pair{ A a;B b; pair()=default; pair(A a,B b):a(a),b(b){} auto operator<=>(const pair&)const=default; }; templatestruct infinity{ templatestatic constexpr T ones(size_t n){return n?ones(n-1)*10+1:0;} templateconstexpr operator T()const{return ones(maxsize10())*(1-neg*2);} }; constexpr infinity oo; void dec(auto&...a){((--a),...);} templateusing pack_back_t=tuple_element_t>; } namespace self{ template>struct map:std::map{ }; } namespace self{ templateistream&operator>>(istream&i,vector&v){fe(v,e)i>>e;return i;} templateconstexpr int depth=0; templatestruct core_t_helper{using type=T;}; templateusing core_t=core_t_helper::type; templatestruct vec; templatestruct hvec_helper{using type=vec::type>;}; templatestruct hvec_helper<0,T>{using type=T;}; templateusing hvec=hvec_helper::type; templatestruct vec:vector{ static constexpr int D=depth+1; using C=core_t; using vector::vector; void resizes(const auto&...a){if constexpr(sizeof...(a)==D)*this=make(a...,C{});else{ }} static auto make(ll n,const auto&...a){ if constexpr(sizeof...(a)==1)return vec(n,array{a...}[0]); else { } } vec&operator--(){fe(*this,e)--e;return*this;} ll size()const{return vector::size();} auto&emplace_back(auto&&...a){vector::emplace_back(std::forward(a)...);return*this;} }; templaterequires(sizeof...(A)>=2)vec(const A&...a)->vec>>; } namespace self{ class DsuPlain{ public: ll n_; vecpar_or_size_; DsuPlain(ll n):n_(n),par_or_size_(n,-1){} auto merge(ll a,ll b){ ll x=leader(a),y=leader(b); if(x==y)return x; if(-par_or_size_[x]<-par_or_size_[y])swap(x,y),swap(a,b); par_or_size_[x]+=par_or_size_[y]; par_or_size_[y]=x; return x; } bool same(ll a,ll b){return leader(a)==leader(b);} ll leader(ll a){ if(par_or_size_[a]<0)return a; return par_or_size_[a]=leader(par_or_size_[a]); } auto groups(){ vecleader_buf(n_),group_size(n_); fo(u,n_){ leader_buf[u]=leader(u); group_size[leader_buf[u]]++; } vec>res(n_); fo(u,n_)res[u].reserve(group_size[u]); fo(u,n_)res[leader_buf[u]].eb(u); res.erase(remove_if(res.begin(),res.end(),[&](const vec&v){return v.empty();}),res.end()); return res; } }; } namespace self{ templatestruct priority_queue:std::priority_queue,F>{ priority_queue()=default; ll size()const{return std::priority_queue,F>::size();} T pop(){T r=this->top();std::priority_queue,F>::pop();return r;} }; templateusing min_heap=priority_queue>; } namespace self{ templatestruct edge{ int from,to; WT wt; int id; edge()=default; edge(int from,int to,WT wt=1,int id=-1):from(from),to(to),wt(wt),id(id){} }; } namespace self{ templateclass Graph{ private: public: ll n_; vec>>edges_; Graph()=default; Graph(ll n):n_(n),edges_(n){} decltype(auto)operator[](ll i){return edges_[i];} void add_edge(ll a,auto&&...b){edges_[a].eb(a,std::forward(b)...);} }; } void self::pp(auto&&...a){const char*c="";((cout<gid(N); fo(k,C)fe(group[k],i)gid[i]=k; Graphg(C); fo(i,M){ if(uf.same(u[i],v[i]))continue; if(i>=61)continue; g.add_edge(gid[u[i]],gid[v[i]],w[i]*pow2(i+1)); g.add_edge(gid[v[i]],gid[u[i]],w[i]*pow2(i+1)); } vecwarp(C,oo); fo(i,N)amin(warp[gid[i]],a[i]); FO(Q){ LL(s,t);dec(s,t); mapdp; dp[gid[s]]=0; min_heap>q; q.emplace(0,gid[s]); while(q.size()){ auto[du,u]=q.pop(); if(dp[u]ep; ep[gid[t]]=0; min_heap>{}.swap(q); q.emplace(0,gid[t]); while(q.size()){ auto[du,u]=q.pop(); if(ep[u]