#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B"
#include<iostream>#include"../cpp/potentialized-unionfind.hpp"intmain(){intn,q;std::cin>>n>>q;UnionFindPlus<longlong>uf(n);while(q--){intt;std::cin>>t;if(t==0){intx,y,z;std::cin>>x>>y>>z;uf.merge(x,y,z);}else{intx,y;std::cin>>x>>y;if(uf.same(x,y))std::cout<<uf.diff(x,y)<<std::endl;elsestd::cout<<'?'<<std::endl;}}}
#line 1 "test/aoj-dsl-1-b.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B"
#include<iostream>#line 2 "cpp/potentialized-unionfind.hpp"
/**
* @file potentialized-unionfind.hpp
* @brief ポテンシャル付きUnionFind
*/#include<cassert>
#include<functional>
#include<stack>
#include<utility>
#include<vector>
#line 2 "cpp/more_functional.hpp"
/**
* @file more_functional.hpp
* @brief 関数オブジェクトを定義する
*/#include<limits>
#include<numeric>
#include<type_traits>namespacemore_functional{template<typenameS>structMax{constSoperator()(constS&a,constS&b)const{returnstd::max(a,b);}};template<typenameS>structMin{constSoperator()(constS&a,constS&b)const{returnstd::min(a,b);}};template<typenameS,std::enable_if_t<std::is_integral_v<S>>*=nullptr>structGcd{constexprSoperator()(constS&a,constS&b)const{returnstd::gcd(a,b);}};template<typenameS>structZero{Soperator()()const{returnS(0);}};template<typenameS>structOne{Soperator()()const{returnS(1);}};template<typenameS>structNone{Soperator()()const{returnS{};}};template<typenameS,std::enable_if_t<std::is_scalar_v<S>>*=nullptr>structMaxLimit{constexprSoperator()()const{returnstd::numeric_limits<S>::max();}};template<typenameS,std::enable_if_t<std::is_scalar_v<S>>*=nullptr>structMinLimit{constexprSoperator()()const{returnstd::numeric_limits<S>::lowest();}};template<typenameS>structDiv{Soperator()(constS&a)const{returnS(1)/a;}};}// namespace more_functional#line 13 "cpp/potentialized-unionfind.hpp"
/**
* @brief ポテンシャル付きUnionFind
* @tparam S ポテンシャルの型
* @tparam Op Sの積のファンクタ
* @tparam E Sの単位元を返すファンクタ
* @tparam Inv Sの逆元を返すファンクタ
*/template<typenameS,classOp,classE,classInv>classPotentializedUnionFind{private:int_n;// 負ならサイズ、非負なら親std::vector<int>parent_or_size;// 重みstd::vector<S>diff_weight;inlineconstexprstaticautoop=Op();inlineconstexprstaticautoe=E();inlineconstexprstaticautoinv=Inv();public:PotentializedUnionFind():_n{},parent_or_size{},diff_weight{}{}/**
* @param n 要素数
*/explicitPotentializedUnionFind(intn):_n(n),parent_or_size(n,-1),diff_weight(n,e()){}/**
* @brief 頂点aの属する連結成分の代表元
*/intleader(inta){assert(0<=a&&a<_n);if(parent_or_size[a]<0)returna;std::stack<int>stk;stk.push(a);while(parent_or_size[stk.top()]>=0){stk.push(parent_or_size[stk.top()]);}constintroot=stk.top();stk.pop();stk.pop();while(!stk.empty()){diff_weight[stk.top()]=op(diff_weight[parent_or_size[stk.top()]],diff_weight[stk.top()]);parent_or_size[stk.top()]=root;stk.pop();}returnroot;}/**
* @brief a のグループと b のグループを統合する
* @param w (b のポテンシャル) - (a のポテンシャル)
* @return 連結したものの代表元
*/intmerge(inta,intb,Sw){assert(0<=a&&a<_n);assert(0<=b&&b<_n);w=op(weight(a),w);w=op(w,inv(weight(b)));intx=leader(a),y=leader(b);if(x==y)returnx;if(-parent_or_size[x]<-parent_or_size[y]){std::swap(x,y);w=inv(w);}parent_or_size[x]+=parent_or_size[y];parent_or_size[y]=x;diff_weight[y]=w;returnx;}/**
* @brief 頂点a,bが連結かどうか
*/boolsame(inta,intb){assert(0<=a&&a<_n);assert(0<=b&&b<_n);returnleader(a)==leader(b);}/**
* @brief (b のポテンシャル) - (a のポテンシャル)
* @remark デフォルトコンストラクタで作られる S について Inv が定義されているならば、a == b を許容
*/Sdiff(inta,intb){assert(same(a,b));returnop(inv(weight(a)),weight(b));}/**
* @brief 頂点aの属する連結成分のサイズ
*/intsize(inta){assert(0<=a&&a<_n);return-parent_or_size[leader(a)];}/**
* @brief グラフを連結成分に分け、その情報を返す
* @return 「一つの連結成分の頂点番号のリスト」のリスト
*/std::vector<std::vector<int>>groups(){std::vector<int>leader_buf(_n),group_size(_n);for(inti=0;i<_n;i++){leader_buf[i]=leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<int>>result(_n);for(inti=0;i<_n;i++){result[i].reserve(group_size[i]);}for(inti=0;i<_n;i++){result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(),result.end(),[&](conststd::vector<int>&v){returnv.empty();}),result.end());returnresult;}private:Sweight(inta){leader(a);returndiff_weight[a];}};/**
* @tparam S 群の型
*/template<typenameS>usingUnionFindPlus=PotentializedUnionFind<S,std::plus<S>,more_functional::None<S>,std::negate<S>>;/**
* @tparam S 群の型
*/template<typenameS>usingUnionFindMul=PotentializedUnionFind<S,std::multiplies<S>,more_functional::One<S>,more_functional::Div<S>>;#line 6 "test/aoj-dsl-1-b.test.cpp"
intmain(){intn,q;std::cin>>n>>q;UnionFindPlus<longlong>uf(n);while(q--){intt;std::cin>>t;if(t==0){intx,y,z;std::cin>>x>>y>>z;uf.merge(x,y,z);}else{intx,y;std::cin>>x>>y;if(uf.same(x,y))std::cout<<uf.diff(x,y)<<std::endl;elsestd::cout<<'?'<<std::endl;}}}