// 誤解法（O(QN)愚直解）チェック
#ifndef INCLUDE_MODE
  #define INCLUDE_MODE
  #define REACTIVE
  // #define USE_GETLINE
#endif

#ifdef INCLUDE_MAIN

inline void Solve()
{
  CEXPR( int , bound_N , 15e5 ); CIN_ASSERT( N , 1 , bound_N );
  CEXPR( int , bound_B , 1e2 ); CIN_ASSERT( B , 1 , bound_B );
  CEXPR( int , bound_Q , 15e2 ); CIN_ASSERT( Q , 1 , bound_Q );
  using mint = DynamicMod;
  mint::SetModulo( B );
  vector<mint> A( N + 1 );
  FOREQ( i , 1 , N ){
    ++( A[i] = A[i-1] );
  }
  CEXPR( ll , bound_d , 1e18 );
  REPEAT( Q ){
    CIN_ASSERT( i , 1 , N );
    CIN_ASSERT( d , 0 , bound_d );
    vector<mint> f( B );
    FOR( j , 0 , B ){
      ++( f[j] = Power( mint::Derepresent( j ) , d ) );
    }
    mint answer{};
    vector<int> dfs{ i };
    while( !dfs.empty() ){
      int temp = dfs.back();
      dfs.pop_back();
      answer += A[temp] = f[A[temp].Represent()];
      if( ( temp <<= 1 ) <= N ){
	if( temp < N ){
	  dfs.push_back( temp | 1 );
	}
	dfs.push_back( temp );
      }
    }
    COUT( answer );
  }
}
REPEAT_MAIN(1);

#else // INCLUDE_MAIN

#ifdef INCLUDE_LIBRARY

// https://github.com/p-adic/cpp
// VVV ライブラリは以下に挿入する。

// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define AS assert
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define LE length
#define PW Power
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
#define VI virtual 
#define IS basic_istream<char,Traits>
#define OS basic_ostream<char,Traits>
#define ST_AS static_assert
#define reMO_CO remove_const
#define is_COructible_v is_constructible_v
#define rBE rbegin
#define reSZ resize

#define RP Represent
#define DeRP Derepresent

TE <TY INT1,TY INT2> CE INT1 RS(INT1 n,CO INT2& M)NE{RE MO(n < 0?((((++n)*= -1)%= M)*= -1)+= M - 1:n < M?n:n %= M);}

TE <int NUM> CL DynamicMods;TE <int NUM>CL COantsForDynamicMods{PU:COantsForDynamicMods()= delete;ST uint g_M;ST uint g_M_minus;ST int g_order_minus_1;ST int g_order_minus_1_neg;ST bool g_M_is_prime;};
TE <int NUM> uint COantsForDynamicMods<NUM>::g_M = 0;TE <int NUM> uint COantsForDynamicMods<NUM>::g_M_minus = -1;TE <int NUM> int COantsForDynamicMods<NUM>::g_order_minus_1 = 0;TE <int NUM> int COantsForDynamicMods<NUM>::g_order_minus_1_neg = 0;TE <int NUM> bool COantsForDynamicMods<NUM>::g_M_is_prime = false;

#define DC_OF_CM_FOR_DYNAMIC_MOD(OPR)IN bool OP OPR(CO DynamicMods<NUM>& n)CO NE
#define DC_OF_AR_FOR_DYNAMIC_MOD(OPR,EX)IN DynamicMods<NUM> OP OPR(DynamicMods<NUM> n)CO EX;
#define DF_OF_CM_FOR_DYNAMIC_MOD(OPR)TE <int NUM> IN bool DynamicMods<NUM>::OP OPR(CO DynamicMods<NUM>& n)CO NE{RE m_n OPR n.m_n;}
#define DF_OF_AR_FOR_DYNAMIC_MOD(OPR,EX,LEFT,OPR2)TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::OP OPR(DynamicMods<NUM> n)CO EX{RE MO(LEFT OPR2 ## = *TH);}TE <int NUM,TY T> IN DynamicMods<NUM> OP OPR(T n0,CO DynamicMods<NUM>& n1)EX{RE MO(DynamicMods<NUM>(MO(n0))OPR ## = n1);}
TE <int NUM>CL DynamicMods{PU:uint m_n;IN DynamicMods()NE;IN DynamicMods(CO DynamicMods<NUM>& n)NE;IN DynamicMods(DynamicMods<NUM>&& n)NE;TE <TY T> IN DynamicMods(T n)NE;IN DynamicMods<NUM>& OP=(DynamicMods<NUM> n)NE;IN DynamicMods<NUM>& OP+=(CO DynamicMods<NUM>& n)NE;IN DynamicMods<NUM>& OP-=(CO DynamicMods<NUM>& n)NE;IN DynamicMods<NUM>& OP*=(CO DynamicMods<NUM>& n)NE;IN DynamicMods<NUM>& OP/=(DynamicMods<NUM> n);TE <TY INT> IN DynamicMods<NUM>& OP<<=(INT n);TE <TY INT> IN DynamicMods<NUM>& OP>>=(INT n);IN DynamicMods<NUM>& OP++()NE;IN DynamicMods<NUM> OP++(int)NE;IN DynamicMods<NUM>& OP--()NE;IN DynamicMods<NUM> OP--(int)NE;DC_OF_CM_FOR_DYNAMIC_MOD(==);DC_OF_CM_FOR_DYNAMIC_MOD(!=);DC_OF_CM_FOR_DYNAMIC_MOD(<);DC_OF_CM_FOR_DYNAMIC_MOD(<=);DC_OF_CM_FOR_DYNAMIC_MOD(>);DC_OF_CM_FOR_DYNAMIC_MOD(>=);DC_OF_AR_FOR_DYNAMIC_MOD(+,NE);DC_OF_AR_FOR_DYNAMIC_MOD(-,NE);DC_OF_AR_FOR_DYNAMIC_MOD(*,NE);DC_OF_AR_FOR_DYNAMIC_MOD(/,);TE <TY INT> IN DynamicMods<NUM> OP^(INT EX)CO;TE <TY INT> IN DynamicMods<NUM> OP<<(INT n)CO;TE <TY INT> IN DynamicMods<NUM> OP>>(INT n)CO;IN DynamicMods<NUM> OP-()CO NE;IN DynamicMods<NUM>& SignInvert()NE;IN DynamicMods<NUM>& Invert();TE <TY INT> IN DynamicMods<NUM>& PW(INT EX);IN VO swap(DynamicMods<NUM>& n)NE;IN CRUI RP()CO NE;ST IN DynamicMods<NUM> DeRP(uint n)NE;ST IN CO DynamicMods<NUM>& Inverse(CRUI n);ST IN CO DynamicMods<NUM>& Factorial(CRUI n);ST IN CO DynamicMods<NUM>& FactorialInverse(CRUI n);ST IN DynamicMods<NUM> Combination(CRUI n,CRUI i);ST IN CO DynamicMods<NUM>& zero()NE;ST IN CO DynamicMods<NUM>& one()NE;ST IN CRUI GetModulo()NE;ST IN VO SetModulo(CRUI M,CRI order_minus_1 = -1)NE;TE <TY INT> IN DynamicMods<NUM>& PositivePW(INT EX)NE;TE <TY INT> IN DynamicMods<NUM>& NonNegativePW(INT EX)NE;US COants = COantsForDynamicMods<NUM>;};
US DynamicMod = DynamicMods<0>;
TE <int NUM> IN DynamicMods<NUM>::DynamicMods()NE:m_n(){}TE <int NUM> IN DynamicMods<NUM>::DynamicMods(CO DynamicMods<NUM>& n)NE:m_n(n.m_n){}TE <int NUM> IN DynamicMods<NUM>::DynamicMods(DynamicMods<NUM>&& n)NE:m_n(MO(n.m_n)){}TE <int NUM> TE <TY T> IN DynamicMods<NUM>::DynamicMods(T n)NE:m_n(RS(uint(MO(n)),COants::g_M)){ST_AS(is_COructible_v<uint,decay_t<T> >);}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP=(DynamicMods<NUM> n)NE{m_n = MO(n.m_n);RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP+=(CO DynamicMods<NUM>& n)NE{(m_n += n.m_n)< COants::g_M?m_n:m_n -= COants::g_M;RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP-=(CO DynamicMods<NUM>& n)NE{m_n < n.m_n?(m_n += COants::g_M)-= n.m_n:m_n -= n.m_n;RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP*=(CO DynamicMods<NUM>& n)NE{m_n = RS(MO(ull(m_n)* n.m_n),COants::g_M);RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP/=(DynamicMods<NUM> n){RE OP*=(n.Invert());}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::OP<<=(INT n){AS(n >= 0);RE *TH *= DynamicMods<NUM>(2).NonNegativePW(MO(n));}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::OP>>=(INT n){AS(n >= 0);WH(n-- > 0){((m_n & 1)== 0?m_n:m_n += COants::g_M)>>= 1;}RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP++()NE{m_n < COants::g_M_minus?++m_n:m_n = 0;RE *TH;}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::OP++(int)NE{DynamicMods<NUM> n{*TH};OP++();RE n;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP--()NE{m_n == 0?m_n = COants::g_M_minus:--m_n;RE *TH;}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::OP--(int)NE{DynamicMods<NUM> n{*TH};OP--();RE n;}DF_OF_CM_FOR_DYNAMIC_MOD(==);DF_OF_CM_FOR_DYNAMIC_MOD(!=);DF_OF_CM_FOR_DYNAMIC_MOD(>);DF_OF_CM_FOR_DYNAMIC_MOD(>=);DF_OF_CM_FOR_DYNAMIC_MOD(<);DF_OF_CM_FOR_DYNAMIC_MOD(<=);DF_OF_AR_FOR_DYNAMIC_MOD(+,NE,n,+);DF_OF_AR_FOR_DYNAMIC_MOD(-,NE,n.SignInvert(),+);DF_OF_AR_FOR_DYNAMIC_MOD(*,NE,n,*);DF_OF_AR_FOR_DYNAMIC_MOD(/,,n.Invert(),*);TE <int NUM> TE <TY INT> IN DynamicMods<NUM> DynamicMods<NUM>::OP^(INT EX)CO{RE MO(DynamicMods<NUM>(*TH).PW(MO(EX)));}TE <int NUM> TE <TY INT> IN DynamicMods<NUM> DynamicMods<NUM>::OP<<(INT n)CO{RE MO(DynamicMods<NUM>(*TH)<<= MO(n));}TE <int NUM> TE <TY INT> IN DynamicMods<NUM> DynamicMods<NUM>::OP>>(INT n)CO{RE MO(DynamicMods<NUM>(*TH)>>= MO(n));}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::OP-()CO NE{RE MO(DynamicMods<NUM>(*TH).SignInvert());}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::SignInvert()NE{m_n > 0?m_n = COants::g_M - m_n:m_n;RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::Invert(){RE m_n <(COants::g_M_is_prime?1e6:3e4)?*TH = Inverse(m_n):NonNegativePW(COants::g_order_minus_1);}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::PositivePW(INT EX)NE{DynamicMods<NUM> PW{*TH};EX--;WH(EX != 0){(EX & 1)== 1?*TH *= PW:*TH;EX >>= 1;PW *= PW;}RE *TH;}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::NonNegativePW(INT EX)NE{RE EX == 0?(m_n = 1,*TH):PositivePW(MO(EX));}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::PW(INT EX){bool neg = EX < 0;RE neg?PositivePW(MO(EX *= COants::g_order_minus_1_neg)):NonNegativePW(MO(EX));}TE <int NUM> IN VO DynamicMods<NUM>::swap(DynamicMods<NUM>& n)NE{std::swap(m_n,n.m_n);}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::Inverse(CRUI n){ST VE<DynamicMods<NUM>> memory ={zero(),one()};ST uint LE_curr = 2;AS(COants::g_M == 1||(0 < n && n < COants::g_M));WH(LE_curr <= n){memory.push_back(COants::g_M_is_prime?DeRP(COants::g_M - memory[COants::g_M % LE_curr].m_n * ull(COants::g_M / LE_curr)% COants::g_M):DeRP(n).NonNegativePW(COants::g_order_minus_1));LE_curr++;}RE memory[n];}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::Factorial(CRUI n){ST VE<DynamicMods<NUM>> memory ={one(),one()};ST uint LE_curr = 2;if(COants::g_M <= n){RE zero();}WH(LE_curr <= n && memory.back().m_n != 0){memory.push_back(memory.back()* DeRP(LE_curr));LE_curr++;}RE LE_curr <= n?memory.back():memory[n];}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::FactorialInverse(CRUI n){ST VE<DynamicMods<NUM>> memory ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory.push_back(memory[LE_curr - 1]* Inverse(LE_curr));LE_curr++;}RE memory[n];}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::Combination(CRUI n,CRUI i){RE i <= n?Factorial(n)* FactorialInverse(i)* FactorialInverse(n - i):zero();}TE <int NUM> IN CRUI DynamicMods<NUM>::RP()CO NE{RE m_n;}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::DeRP(uint n)NE{DynamicMods<NUM> n_copy{};n_copy.m_n = MO(n);RE n_copy;}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::zero()NE{ST CO DynamicMods<NUM> z{};RE z;}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::one()NE{ST CO DynamicMods<NUM> o{1};RE o;}TE <int NUM> IN CRUI DynamicMods<NUM>::GetModulo()NE{RE COants::g_M;}TE <int NUM> IN VO DynamicMods<NUM>::SetModulo(CRUI M,CRI order_minus_1)NE{COants::g_M = M;COants::g_M_minus = M - 1;COants::g_order_minus_1 = order_minus_1 == -1?M - 2:order_minus_1;COants::g_order_minus_1_neg = -COants::g_order_minus_1;COants::g_M_is_prime = order_minus_1 == -1;}TE <int NUM> IN DynamicMods<NUM> Inverse(CO DynamicMods<NUM>& n){RE MO(DynamicMods<NUM>(n).Invert());}TE <int NUM,TY INT> IN DynamicMods<NUM> PW(DynamicMods<NUM> n,INT EX){RE MO(n.PW(MO(EX)));}TE <int NUM> IN VO swap(DynamicMods<NUM>& n0,DynamicMods<NUM>& n1)NE{n0.swap(n1);}TE <int NUM> IN string to_string(CO DynamicMods<NUM>& n)NE{RE to_string(n.RP())+ " + " + to_string(DynamicMods<NUM>::GetModulo())+ "Z";}TE <int NUM,CL Traits> IN IS& OP>>(IS& is,DynamicMods<NUM>& n){ll m;is >> m;n = m;RE is;}TE <int NUM,CL Traits> IN OS& OP<<(OS& os,CO DynamicMods<NUM>& n){RE os << n.RP();}

// AAA ライブラリは以上に挿入する。

#define INCLUDE_MAIN
#include __FILE__

#else // INCLUDE_LIBRARY

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE2 )
  #define SIGNAL signal( SIGABRT , &AlertAbort );
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl
  #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl
  #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl
  #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define SIGNAL 
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 )
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL
  #define CERR_A( N , A ) 
  #define COUT_A( N , A ) OUTPUT_ARRAY( cout , N , A ) << ENDL
  #define CERR_ITR( A ) 
  #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL
#endif
#ifdef REACTIVE
  #define ENDL endl
#else
  #define ENDL "\n"
#endif
#ifdef USE_GETLINE
  #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); }
  #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
  #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
#else
  #define SET_LL( A ) cin >> A
  #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )
  #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , __VA_ARGS__ ); }
  #define CIN_A( LL , I , N , ... ) VE<LL> __VA_ARGS__; SET_A( I , N , __VA_ARGS__ );
  #define CIN_AA( LL , I0 , N0 , I1 , N1 , VAR ) VE<VE<LL>> VAR( N0 + I0 ); FOR( VARIABLE_FOR_CIN_AA , 0 , N0 ){ SET_A( I1 , N1 , VAR[VARIABLE_FOR_CIN_AA + I0] ); }
#endif
#include <bits/stdc++.h>
using namespace std;
#define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ CERR( "テストケースの個数を入力してください。" ); SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } }
#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now()
#define CURRENT_TIME static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 )
#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 )
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX )
#define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); }
#define SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_AA0 , 0 , N0 ){ FOR( VARIABLE_FOR_SET_AA1 , 0 , N1 ){ SET_ASSERT( A[VARIABLE_FOR_SET_AA0 + I0][VARIABLE_FOR_SET_AA1 + I1] , MIN , MAX ); } }
#define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX )
#define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector<decldecay_t( MAX )> A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX )
#define CIN_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) vector A( N0 + I0 , vector<decldecay_t( MAX )>( N1 + I1 ) ); SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > FINAL ; VAR -- )
#define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN()
#define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define RUN( ARRAY , ... ) for( auto&& __VA_ARGS__ : ARRAY )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )
#define RETURN( ... ) COUT( __VA_ARGS__ ); return

// 型のエイリアス
#define decldecay_t( VAR ) decay_t<decltype( VAR )>
template <typename F , typename...Args> using ret_t = decltype( declval<F>()( declval<Args>()... ) );
template <typename T> using inner_t = typename T::type;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lld = __float128;
template <typename INT> using T2 = pair<INT,INT>;
template <typename INT> using T3 = tuple<INT,INT,INT>;
template <typename INT> using T4 = tuple<INT,INT,INT,INT>;
using path = pair<int,ll>;

// 入出力用
template <class Traits , typename T , typename U , template <typename...> typename V> inline auto operator>>( basic_istream<char,Traits>& is , V<T,U>& arg ) -> decltype((get<0>(arg),is))& { return is >> get<0>( arg ) >> get<1>( arg ); }
template <class Traits , typename T , typename U , typename V> inline basic_istream<char,Traits>& operator>>( basic_istream<char,Traits>& is , tuple<T,U,V>& arg ) { return is >> get<0>( arg ) >> get<1>( arg ) >> get<2>( arg ); }
template <class Traits , typename T , typename U , typename V , typename W> inline basic_istream<char,Traits>& operator>>( basic_istream<char,Traits>& is , tuple<T,U,V,W>& arg ) { return is >> get<0>( arg ) >> get<1>( arg ) >> get<2>( arg ) >> get<3>( arg ); }

template <class Traits , typename T , typename U , template <typename...> typename V> inline auto operator<<( basic_ostream<char,Traits>& os , const V<T,U>& arg ) -> decltype((get<0>(arg),os))& { return os << get<0>( arg ) << " " << get<1>( arg ); }
template <class Traits , typename T , typename U , typename V> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const tuple<T,U,V>& arg ) { return os << get<0>( arg ) << " " << get<1>( arg ) << " " << get<2>( arg ); }
template <class Traits , typename T , typename U , typename V , typename W> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const tuple<T,U,V,W>& arg ) { return os << get<0>( arg ) << " " << get<1>( arg ) << " " << get<2>( arg ) << " " << get<3>( arg ); }

#define DEFINITION_OF_COUT_FOR_VECTOR( V ) template <class Traits , typename Arg> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const V<Arg>& arg ) { auto begin = arg.begin() , end = arg.end(); auto itr = begin; while( itr != end ){ ( itr == begin ? os : os << " " ) << *itr; itr++; } return os; }
DEFINITION_OF_COUT_FOR_VECTOR( vector );
DEFINITION_OF_COUT_FOR_VECTOR( list );
DEFINITION_OF_COUT_FOR_VECTOR( set );
DEFINITION_OF_COUT_FOR_VECTOR( unordered_set );

inline void VariadicResize( const int& size ) {}
template <typename Arg , typename... ARGS> inline void VariadicResize( const int& size , Arg& arg , ARGS&... args ) { arg.resize( size ); VariadicResize( size , args... ); }

template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicSet( basic_istream<char,Traits>& is , const int& i ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicSet( basic_istream<char,Traits>& is , const int& i , Arg& arg , ARGS&... args ) { return VariadicSet( is >> arg[i] , i , args... ); }

template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }

template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os << arg; }
template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }

// デバッグ用
#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif

#define INCLUDE_LIBRARY
#include __FILE__

#endif // INCLUDE_LIBRARY

#endif // INCLUDE_MAIN