------------------------------------------------
/* in the name of Allah */ #include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; /* Math */ template < class T > inline T GCD(T a , T b){ if(a < 0) return GCD(-a , b) ; if(b < 0) return GCD(a , -b) ; return (b == 0) ? a : GCD(b , a % b) ; } template < class T > inline T LCM(T a , T b){ if(a < 0) return LCM(-a , b) ; if(b < 0) return LCM(a , -b) ; return a * (b / GCD(a , b)) ; } template < class T > inline bool isPrime(T n){ if(n < 2) return false ; for(T i = 2 ; i * i <= n ; i++) if(n % i == 0) return false ; return true ; } template < class T > vector <T> Divisor(T num){ vector <T> res ; res.clear() ; for(int i = 1 ; i <= num/2 ; i++) if(num % i == 0) res.push_back(i) ; return res ; } template < class T , class M > inline T POWER(T x , M y){/* (x ^ y) compute to 2^63 */ T temp = 1 ; if(y == 0) return 1 ; for(int i = 1 ; i <= y ; i++) temp *= x ; return temp ;} /* Manipulation */ template < class T , class M > bool Exist(T x , M element) { for(int i = 0 ; i < x.size() ; i++) if(x[i] == element) return true ; return false ; } template < class T > vector <T> Unique(vector <T> v){ T temp ; vector <T> res ; res.clear() ; for(int i = 0 ; i < v.size() ; i++){temp = v[i] ; if(Exist(res,temp) == false) res.push_back(temp) ; } return res ; } template < class T > vector <T> Parse(T temp){ vector <T> ans ; ans.clear() ; T s ; istringstream is(temp) ; while(is >> s){ ans.push_back(s) ; } return ans ; } template < class T > string toString(T x) {stringstream s ; s << x; return s.str() ; } template < class T > long long toInt(T x) {istringstream is(x) ; long long num ; is >> num ; return num ; } template< class T > inline void checkMin(T &a , T b){ if(b < a) a = b ; } template< class T > inline void checkMax(T &a , T b){ if(b > a) a = b ; } bool isLowerCase(char c){ return (c >= 'a' && c <= 'z') ; } bool isUpperCase(char c){ return (c >= 'A' && c <= 'Z') ; } char toLowerCase(char c){ return (isUpperCase(c) ? (c + 32) : c) ; } char toUpperCase(char c){ return (isLowerCase(c) ? (c - 32) : c) ; } bool isLetter ( char c ){ return (isUpperCase(c)) || (isLowerCase(c)) ; } bool isDigit ( char c ){ return (c >= '0' && c <= '9') ; } /* Debug */ template < class T > void print(T ans){ for(unsigned int i = 0 ; i < ans.size() ; i++ ) cout << ans[i] << " " ; cout << endl ; } template < class T > void print2(T ans){ cout << ans ; cout << endl ; } typedef long long LL ; #define ALL(a) (a).begin(),(a).end() #define SZ(v) ((int)(v).size()) #define Clear(x,with) memset(x , with , sizeof(x)) #define FOR(i,start,end) for(int i = start ; i < end ; i++) #define REP(i,start,end) for(int i = start ; i >= end ; i--) #define FOREACH(it,x) for(__typeof((x).begin()) it = (x.begin()) ; it != (x).end() ; it++) class ClassName { public : Function { int ans = 0 ; return ans ; } };