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")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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);
}
template<typename C> // container
inline void sort(C& v) {
    sort(v.begin(), v.end());
}
inline void println(int u) { printf("%d\n", u); }
inline void printsp(int u) { printf("%d ", u); }
#define all(v) v.begin(), v.end()
#define rep(x, st, en) for(int x = st; x < en; x++)
#define fwi(i, c, source) { int i = 0; for(auto c : source) { 
#define efwi(i) i++; } }
#define pb push_back
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX