1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//#pragma comment(linker, "/STACK:1024000000,1024000000")
/* vim: set fdm=marker */
//{{{
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int iinf = 0x7fffffff;
const ll linf = ~(1LL<<63);
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<ll, int> mli;
typedef map<ll, ll> mll;
template<typename T>
inline T gcd(T a, T b) {
    if(a < 0) return gcd(-a, b);
    if(b < 0) return gcd( a,-b);
    if(a < b) return gcd(b, a);
    if(b == 0) return a;
    return gcd(b, a%b);
}
ll qpow(ll a, ll n, ll mod) {
    a %= mod;
    ll ans = 1LL;
    while(n) {
        if(n & 1) ans = (ans*a % mod);
        a = (a*a % mod);
        n >>= 1;
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX