cp_template.cpp

/*
Fast I/O Template for Competitive Programming
Mathematical Foundation: Optimized input/output for large datasets
sync_with_stdio(false) - decouples C++ streams from C stdio
cin.tie(nullptr) - unties cin from cout for faster input
Applications: Contest problems with large input (10^6+ operations)
*/

#include <bits/stdc++.h>
using namespace std;

// Fast I/O setup
void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

// Competitive Programming Template
class CP {
public:
    // Fast I/O
    template<typename T> void read(T& x) { cin >> x; }
    template<typename T> void write(T x) { cout << x; }
    template<typename T> void writeln(T x) { cout << x << '\n'; }
    
    // Multiple inputs
    template<typename T> void readVec(vector<T>& v, int n) {
        v.resize(n);
        for (int i = 0; i < n; i++) cin >> v[i];
    }
    
    // Debug output (only in debug mode)
    #ifdef DEBUG
    template<typename T> void debug(T x) { cerr << "[DEBUG] " << x << '\n'; }
    template<typename T> void debugVec(vector<T>& v) {
        cerr << "[DEBUG] ";
        for (auto x : v) cerr << x << " ";
        cerr << '\n';
    }
    #else
    template<typename T> void debug(T x) {}
    template<typename T> void debugVec(vector<T>& v) {}
    #endif
};

// Global CP instance
CP cp;

// Commonly used macros
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define F first
#define S second

// Constants
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int MAXN = 1e6 + 5;

// Direction arrays for 4-directional movement
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// Direction arrays for 8-directional movement
int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

// Utility functions
template<typename T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T power(T base, T exp, T mod = MOD) {
    T result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// String to integer conversion
ll stringToInt(string s) {
    ll result = 0;
    for (char c : s) result = result * 10 + (c - '0');
    return result;
}

// Check if number is prime
bool isPrime(ll n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ll i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// Fast matrix multiplication for DP optimization
vector<vector<ll>> matMul(vector<vector<ll>>& A, vector<vector<ll>>& B, int mod = MOD) {
    int n = A.size(), m = B[0].size(), p = B.size();
    vector<vector<ll>> C(n, vector<ll>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < p; k++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    return C;
}

// Matrix exponentiation
vector<vector<ll>> matPow(vector<vector<ll>> base, ll exp, int mod = MOD) {
    int n = base.size();
    vector<vector<ll>> result(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1; // Identity matrix
    
    while (exp > 0) {
        if (exp % 2 == 1) result = matMul(result, base, mod);
        base = matMul(base, base, mod);
        exp /= 2;
    }
    return result;
}

// Binary lifting for LCA preprocessing
class BinaryLifting {
    vector<vector<int>> up;
    vector<int> depth;
    int LOG;
    
public:
    BinaryLifting(vector<vector<int>>& adj, int root = 0) {
        int n = adj.size();
        LOG = ceil(log2(n)) + 1;
        up.assign(n, vector<int>(LOG, -1));
        depth.assign(n, 0);
        
        function<void(int, int)> dfs = [&](int v, int p) {
            up[v][0] = p;
            for (int i = 1; i < LOG; i++) {
                if (up[v][i-1] != -1) up[v][i] = up[up[v][i-1]][i-1];
            }
            for (int u : adj[v]) {
                if (u != p) {
                    depth[u] = depth[v] + 1;
                    dfs(u, v);
                }
            }
        };
        dfs(root, -1);
    }
    
    int lca(int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);
        int diff = depth[a] - depth[b];
        for (int i = 0; i < LOG; i++) {
            if ((diff >> i) & 1) a = up[a][i];
        }
        if (a == b) return a;
        for (int i = LOG - 1; i >= 0; i--) {
            if (up[a][i] != up[b][i]) {
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    }
};

// Coordinate compression
class CoordCompress {
    vector<int> vals;
public:
    void add(int x) { vals.pb(x); }
    void build() { sort(all(vals)); vals.erase(unique(all(vals)), vals.end()); }
    int get(int x) { return lower_bound(all(vals), x) - vals.begin(); }
    int size() { return sz(vals); }
};

// Basic template for contest problems
void solve() {
    // Read input
    int n;
    cp.read(n);
    
    vi a(n);
    cp.readVec(a, n);
    
    // Solve the problem
    // ...
    
    // Output result
    cp.writeln("Answer");
}

// Main function template
int main() {
    fastIO();
    
    int t = 1;
    // cin >> t; // Uncomment for multiple test cases
    
    while (t--) {
        solve();
    }
    
    return 0;
}

/*
Usage Example:

int main() {
    fastIO();
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        
        // Your solution here
        
        cout << "Answer\n";
    }
    
    return 0;
}
*/