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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor: initialize with value, no children
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// BST Search — O(log N) average, O(N) worst case
// Returns pointer to node with value 'target', or nullptr if not found
TreeNode* search(TreeNode* root, int target) {
    // Base case: empty tree or found target
    if (root == nullptr || root->val == target) {
        return root;
    }
    // BST property: target is smaller, go left
    if (target < root->val) {
        return search(root->left, target);
    }
    // target is larger, go right
    return search(root->right, target);
}

// BST Insert — O(log N) average
// Returns the root of the subtree (possibly new)
TreeNode* insert(TreeNode* root, int val) {
    // Reached an empty spot — create new node here
    if (root == nullptr) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);   // Recurse left
    } else if (val > root->val) {
        root->right = insert(root->right, val); // Recurse right
    }
    // val == root->val: duplicate, ignore (or handle as needed)
    return root;
}

// Usage:
// TreeNode* root = nullptr;
// root = insert(root, 5);
// root = insert(root, 3);
// root = insert(root, 8);

// BST Delete — O(log N) average
// Helper: find minimum node in subtree
TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) node = node->left;
    return node;
}

// Delete node with value 'val' from tree rooted at 'root'
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) return nullptr;  // Value not found

    if (val < root->val) {
        // Case: target is in left subtree
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        // Case: target is in right subtree
        root->right = deleteNode(root->right, val);
    } else {
        // Found the node to delete!

        // Case 1: No children (leaf node)
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // Case 2A: Only right child
        else if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        // Case 2B: Only left child
        else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // Case 3: Two children — replace with in-order successor
        else {
            TreeNode* successor = findMin(root->right);  // Smallest in right subtree
            root->val = successor->val;                  // Copy successor's value
            root->right = deleteNode(root->right, successor->val);  // Delete successor
        }
    }
    return root;
}

// Pre-order Traversal — O(N) time, O(H) space (H = height)
// Visit order: root, left subtree, right subtree
void preorder(TreeNode* root) {
    if (root == nullptr) return;   // Base case
    cout << root->val << " ";      // Process root first
    preorder(root->left);          // Then left subtree
    preorder(root->right);         // Then right subtree
}

// For tree:    [5]
//             /    \
//           [3]    [8]
//          /   \
//        [1]   [4]
// Pre-order: 5 3 1 4 8

// Pre-order traversal — iterative version
void preorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> stk;
    stk.push(root);

    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        cout << node->val << " ";    // Process current node

        // Push right first (so left is processed first — LIFO!)
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
}

// In-order Traversal — O(N) time
// Visit order: left subtree, root, right subtree
// Key property: In-order traversal of a BST produces sorted output!
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);           // Left subtree first
    cout << root->val << " ";      // Then root
    inorder(root->right);          // Then right subtree
}

// For BST (values {1, 3, 4, 5, 8}):
// In-order: 1 3 4 5 8  ← Sorted! This is the most important BST property

// In-order traversal — iterative version
void inorderIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* curr = root;

    while (curr != nullptr || !stk.empty()) {
        // Go as far left as possible
        while (curr != nullptr) {
            stk.push(curr);
            curr = curr->left;
        }
        // Process the leftmost unprocessed node
        curr = stk.top(); stk.pop();
        cout << curr->val << " ";

        // Move to right subtree
        curr = curr->right;
    }
}

// Post-order Traversal — O(N) time
// Visit order: left subtree, right subtree, root
// Used for: deleting trees, evaluating expression trees
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);         // Left subtree first
    postorder(root->right);        // Then right subtree
    cout << root->val << " ";      // Root last
}

// ── Use post-order to free memory ──
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);   // Delete left subtree first
    deleteTree(root->right);  // Then right subtree
    delete root;              // Finally delete this node (safe: children already deleted)
}

// Level-order Traversal (BFS) — O(N) time, O(W) space (W = max level width)
// Uses a queue: processes nodes level by level
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();  // Number of nodes at current level

        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            cout << node->val << " ";

            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << "\n";  // Newline between levels
    }
}

// For BST [5, 3, 8, 1, 4]:
// Level 0: 5
// Level 1: 3 8
// Level 2: 1 4

// Tree Height — O(N) time, O(H) recursive stack space
// Height = length of the longest root-to-leaf path
// Convention: empty tree height = -1, leaf node height = 0
int height(TreeNode* root) {
    if (root == nullptr) return -1;  // Empty subtree height -1

    int leftHeight  = height(root->left);   // Left subtree height
    int rightHeight = height(root->right);  // Right subtree height

    return 1 + max(leftHeight, rightHeight);  // +1 for current node
}

// Check balanced BST — O(N) time
// Returns -1 if unbalanced, otherwise returns subtree height
int checkBalanced(TreeNode* root) {
    if (root == nullptr) return 0;  // Empty tree is balanced, height 0

    int leftH = checkBalanced(root->left);
    if (leftH == -1) return -1;     // Left subtree unbalanced

    int rightH = checkBalanced(root->right);
    if (rightH == -1) return -1;    // Right subtree unbalanced

    // Check current node's balance: height difference at most 1
    if (abs(leftH - rightH) > 1) return -1;  // Unbalanced!

    return 1 + max(leftH, rightH);   // Return height when balanced
}

bool isBalanced(TreeNode* root) {
    return checkBalanced(root) != -1;
}

// Node count — O(N)
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Count leaf nodes specifically
int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;  // Leaf!
    return countLeaves(root->left) + countLeaves(root->right);
}

          [1]
         /    \
       [2]    [3]
      /   \      \
    [4]   [5]   [6]
   /
  [7]

LCA(4, 5) = 2     (4 and 5 are both descendants of 2)
LCA(4, 6) = 1     (deepest common ancestor is root 1)
LCA(2, 4) = 2     (node 2 is an ancestor of 4, and also its own ancestor)

// LCA Brute Force — O(N) per query
// Strategy: find path from root to each node, then find last common node

// Step 1: Find path from root to target node
bool findPath(TreeNode* root, int target, vector<int>& path) {
    if (root == nullptr) return false;

    path.push_back(root->val);  // Add current node to path

    if (root->val == target) return true;  // Found target!

    // Try left subtree first, then right
    if (findPath(root->left, target, path)) return true;
    if (findPath(root->right, target, path)) return true;

    path.pop_back();  // Backtrack: target not in this subtree
    return false;
}

// Step 2: Use two paths to find LCA
int lca(TreeNode* root, int u, int v) {
    vector<int> pathU, pathV;

    findPath(root, u, pathU);   // Path from root to u
    findPath(root, v, pathV);   // Path from root to v

    // Find last common node in both paths
    int result = root->val;
    int minLen = min(pathU.size(), pathV.size());

    for (int i = 0; i < minLen; i++) {
        if (pathU[i] == pathV[i]) {
            result = pathU[i];  // Still common
        } else {
            break;  // Diverged
        }
    }
    return result;
}

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

struct BST {
    TreeNode* root;
    BST() : root(nullptr) {}

    // ── Insert ──
    TreeNode* _insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->val) node->left  = _insert(node->left,  val);
        else if (val > node->val) node->right = _insert(node->right, val);
        return node;
    }
    void insert(int val) { root = _insert(root, val); }

    // ── Search ──
    bool search(int val) {
        TreeNode* curr = root;
        while (curr) {
            if (val == curr->val) return true;
            curr = (val < curr->val) ? curr->left : curr->right;
        }
        return false;
    }

    // ── In-order traversal (sorted output) ──
    void _inorder(TreeNode* node, vector<int>& result) {
        if (!node) return;
        _inorder(node->left, result);
        result.push_back(node->val);
        _inorder(node->right, result);
    }
    vector<int> getSorted() {
        vector<int> result;
        _inorder(root, result);
        return result;
    }

    // ── Height ──
    int _height(TreeNode* node) {
        if (!node) return -1;
        return 1 + max(_height(node->left), _height(node->right));
    }
    int height() { return _height(root); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    BST bst;
    vector<int> vals = {5, 3, 8, 1, 4, 7, 10};
    for (int v : vals) bst.insert(v);

    cout << "Sorted output: ";
    for (int v : bst.getSorted()) cout << v << " ";
    cout << "\n";
    // Output: 1 3 4 5 7 8 10

    cout << "Height: " << bst.height() << "\n";  // 2
    cout << "Search 4: " << bst.search(4) << "\n";  // 1 (true)
    cout << "Search 6: " << bst.search(6) << "\n";  // 0 (false)

    return 0;
}

// Cow Family Tree — Depth Queries
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> children[MAXN];  // Adjacency list: children[i] = list of i's children
int depth[MAXN];             // depth[i] = depth of node i

// DFS to compute depths
void dfs(int node, int d) {
    depth[node] = d;
    for (int child : children[node]) {
        dfs(child, d + 1);  // Children have depth +1
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 2; i <= n; i++) {
        int par;
        cin >> par;
        children[par].push_back(i);  // par is i's parent
    }

    dfs(1, 0);  // Start DFS from root (cow 1) at depth 0

    while (m--) {
        int x;
        cin >> x;
        cout << depth[x] << "\n";
    }

    return 0;
}
// Time: O(N + M)
// Space: O(N)

// Reconstruct tree from pre-order + in-order — O(N^2) naive
TreeNode* build(vector<int>& pre, int preL, int preR,
                vector<int>& in,  int inL,  int inR) {
    if (preL > preR) return nullptr;

    int rootVal = pre[preL];  // First element of pre-order = root
    TreeNode* root = new TreeNode(rootVal);

    // Find root in in-order array
    int rootIdx = inL;
    while (in[rootIdx] != rootVal) rootIdx++;

    int leftSize = rootIdx - inL;  // Number of nodes in left subtree

    // Recursively build left and right subtrees
    root->left  = build(pre, preL+1, preL+leftSize, in, inL, rootIdx-1);
    root->right = build(pre, preL+leftSize+1, preR, in, rootIdx+1, inR);

    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    return build(preorder, 0, n-1, inorder, 0, n-1);
}

// ❌ Wrong: No null pointer check!
void inorder(TreeNode* root) {
    inorder(root->left);  // Crashes when root is null
    cout << root->val;
    inorder(root->right);
}

// ✅ Correct: Always check for null first
void inorder(TreeNode* root) {
    if (root == nullptr) return;  // ← Critical!
    inorder(root->left);
    cout << root->val;
    inorder(root->right);
}

// ❌ Dangerous: degenerate tree (skewed) with 10^5 nodes
// Recursion depth = 10^5, default stack ~8MB, overflows at ~10^4~10^5!

// ✅ Safe: use iterative for large trees
void dfsIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    if (root) stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        process(node);
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
}

Core Idea: Pass down an allowed (min, max) range; each node must be strictly within its range.

#include <bits/stdc++.h>
using namespace std;
struct TreeNode { int val; TreeNode *left, *right; };

bool isValidBST(TreeNode* root, long long lo, long long hi) {
    if (!root) return true;
    if (root->val <= lo || root->val >= hi) return false;
    return isValidBST(root->left, lo, root->val)
        && isValidBST(root->right, root->val, hi);
}
// Usage: isValidBST(root, LLONG_MIN, LLONG_MAX);

Why do we need min/max bounds? Because a node in the right subtree of the root, even if it's the left child of some ancestor, must still be > root. Passing only the direct parent is insufficient.

Complexity: O(N) time, O(H) recursive stack.

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        if (--k == 0) return cur->val;
        cur = cur->right;
    }
    return -1;
}

Complexity: O(H + K) — much better than O(N) for small K.

Core Idea: Post-order DFS. Each node computes: (a) its own height for the parent; (b) the best path through it (updates global answer).

int diameter = 0;
int height(TreeNode* root) {
    if (!root) return 0;
    int L = height(root->left);
    int R = height(root->right);
    diameter = max(diameter, L + R);  // Path through this node: L edges left + R edges right
    return 1 + max(L, R);              // Height returned to parent
}
// Answer: diameter (in edges). For node count, diameter+1.

Why does this work? The diameter must pass through some "apex" node — the highest node on the path. That node's contribution = height(left) + height(right). We visit every node as a potential apex.

Complexity: O(N).

void inorder(TreeNode* root, vector<int>& arr) {
    if (!root) return;
    inorder(root->left, arr);
    arr.push_back(root->val);
    inorder(root->right, arr);
}

int findMedian(TreeNode* root) {
    vector<int> arr;
    inorder(root, arr);
    return arr[(arr.size() - 1) / 2];  // Lower median for even N
}

Optimization for large trees: Use the K-th smallest method from Problem 3.11.2 directly — no need to flatten: kthSmallest(root, (n+1)/2), saves O(N) memory.

Complexity: O(N) time and space (or O(H + N/2) with K-th smallest).

Core Idea: DFS returns "best single-sided path going down from this node". Global answer considers "best double-sided path with this node as apex". Negative sub-paths are clamped to 0 (don't include them).

int bestSum = INT_MIN;
int maxGain(TreeNode* root) {
    if (!root) return 0;
    // Clamp to 0: can choose not to include subtree (if it's negative)
    int L = max(0, maxGain(root->left));
    int R = max(0, maxGain(root->right));

    // Best path with root as turning point
    bestSum = max(bestSum, root->val + L + R);

    // Return single-sided path to parent (can only choose one branch)
    return root->val + max(L, R);
}
// Answer: bestSum after calling maxGain(root)

Key Insight: The path is "V"-shaped — goes up to some apex, then comes down. Each node is considered as apex exactly once.

Complexity: O(N).

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

const int MAXN = 500005, LOG = 20;
vector<int> adj[MAXN];
int depth[MAXN], anc[MAXN][LOG];

// DFS to build tree, computing anc[v][k]
void dfs(int u, int par, int d) {
    depth[u] = d;
    anc[u][0] = par;  // Direct parent
    for (int k = 1; k < LOG; k++)
        anc[u][k] = anc[anc[u][k-1]][k-1];  // Build by doubling
    for (int v : adj[u])
        if (v != par) dfs(v, u, d + 1);
}

// O(log N) LCA query
int lca(int u, int v) {
    // Step 1: Bring the deeper node up to the same depth
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; k++)
        if ((diff >> k) & 1) u = anc[u][k];
    
    // Step 2: Both at same depth, jump together until they meet
    if (u == v) return u;  // One was already an ancestor of the other
    for (int k = LOG - 1; k >= 0; k--)
        if (anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    return anc[u][0];  // Now u, v's parent is the LCA
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1, 0);  // Root is 1, root's parent is itself
    while (q--) {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}

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

const int MAXN = 100005;
vector<int> children[MAXN];
int val[MAXN];
int in_time[MAXN], out_time[MAXN], timer_val = 0;
int euler_arr[MAXN];   // euler_arr[in_time[u]] = val[u]

void dfs_euler(int u, int parent) {
    in_time[u] = ++timer_val;       // Entry: record timestamp
    euler_arr[timer_val] = val[u];  // Record value in flattened array
    
    for (int v : children[u]) {
        if (v != parent) dfs_euler(v, u);
    }
    
    out_time[u] = timer_val;        // Exit: record final timestamp
}

// Query sum of all values in subtree of node u
// Using prefix sum array 'prefix' preprocessed from euler_arr
int subtree_sum(int u, int prefix[]) {
    return prefix[out_time[u]] - prefix[in_time[u] - 1];
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        children[u].push_back(v);
        children[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> val[i];
    
    dfs_euler(1, -1);  // Start from root 1
    
    // Build prefix sums
    int prefix[MAXN] = {};
    for (int i = 1; i <= n; i++)
        prefix[i] = prefix[i-1] + euler_arr[i];
    
    // Query subtree sum of node u
    int u; cin >> u;
    cout << subtree_sum(u, prefix) << "\n";
    return 0;
}

Approach: Post-order DFS, accumulate from leaves upward.

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<long long> val(n + 1);
    for (int i = 1; i <= n; i++) cin >> val[i];
    
    vector<vector<int>> children(n + 1);
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        children[p].push_back(i);
    }
    
    vector<long long> sub(n + 1);
    function<void(int)> dfs = [&](int u) {
        sub[u] = val[u];
        for (int v : children[u]) { dfs(v); sub[u] += sub[v]; }
    };
    dfs(1);
    
    for (int i = 1; i <= n; i++) cout << sub[i] << " \n"[i==n];
    return 0;
}

Complexity: O(N) time and space.

Approach: Two BFS — first find the farthest node u, then find the diameter from u.

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

int n;
vector<int> adj[100005];

pair<int,int> bfs_far(int src) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[src] = 0; q.push(src);
    int far = src;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > dist[far]) far = v;
            }
        }
    }
    return {far, dist[far]};
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    auto [u, _] = bfs_far(1);
    auto [v, d] = bfs_far(u);
    cout << d << "\n";
    return 0;
}

Use the Binary Lifting LCA implementation from §5.5.1:

// See §5.5.1 complete implementation (dfs preprocessing + lca query function)
// In main():
int n, q; cin >> n >> q;
// Read tree, dfs(1, 1, 0), then q queries of lca(u, v)

Trace (tree: 1-2-3-4 chain, query lca(4,1)):

depth = [_, 0, 1, 2, 3]
anc[4][0]=3, anc[4][1]=1 (parent of parent of 3), anc[3][0]=2, ...

lca(4, 1): depth[4]=3 > depth[1]=0
  diff=3=0b11, k=0: (diff>>0)&1=1, u=anc[4][0]=3
  k=1: (diff>>1)&1=1, u=anc[3][1]=1
  Now depth[1]=depth[1]=0, u==v=1, return 1 ✓

Approach: Build Euler Tour, then use prefix sum array for O(1) per query.

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

const int MAXN = 100005;
vector<int> adj[MAXN];
long long val[MAXN];
int in_t[MAXN], out_t[MAXN], timer_v = 0;
long long ea[MAXN];  // Euler Tour flattened value array

void dfs(int u, int par) {
    in_t[u] = ++timer_v;
    ea[timer_v] = val[u];
    for (int v : adj[u])
        if (v != par) dfs(v, u);
    out_t[u] = timer_v;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    cin >> q;
    
    dfs(1, -1);
    
    // Prefix sums
    long long prefix[MAXN] = {};
    for (int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + ea[i];
    
    while (q--) {
        int u; cin >> u;
        cout << prefix[out_t[u]] - prefix[in_t[u]-1] << "\n";
    }
    return 0;
}

Why is this correct? The Euler Tour guarantees that subtree nodes of u occupy exactly the interval [in_t[u], out_t[u]], and prefix sums answer range sum queries in O(1).

Using Kruskal's algorithm (Union-Find covered in Chapter 5.6):

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

vector<int> par, rnk;
int find(int x) { return par[x]==x ? x : par[x]=find(par[x]); }
bool unite(int x, int y) {
    x=find(x); y=find(y);
    if (x==y) return false;
    if (rnk[x]<rnk[y]) swap(x,y);
    par[y]=x; if(rnk[x]==rnk[y]) rnk[x]++;
    return true;
}

int main() {
    int n, m; cin >> n >> m;
    par.resize(n+1); rnk.assign(n+1,0);
    iota(par.begin(),par.end(),0);
    
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w,u,v] : edges) cin >> u >> v >> w;
    sort(edges.begin(), edges.end());
    
    long long ans = 0; int cnt = 0;
    for (auto [w,u,v] : edges)
        if (unite(u,v)) { ans+=w; if(++cnt==n-1) break; }
    
    cout << (cnt==n-1 ? to_string(ans) : "IMPOSSIBLE") << "\n";
    return 0;
}