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

// =====================================================================
// This file contains a collection of Trie (Prefix Tree) algorithms.
// Each function is ready to be used as a "black box".
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
//
// TERMINOLOGY:
//   - Trie (pronounced "try"): a tree structure used to store strings,
//     where each node represents a single character. All descendants of
//     a node share a common prefix (hence "prefix tree").
//   - Node: an element of the Trie, contains child pointers.
//   - Root: the topmost node, represents an empty string.
//   - End of word (isEnd): a flag indicating that a complete word ends
//     at this node.
//   - Prefix count: number of words that have this node as a prefix.
//   - Word count: number of times a word has been inserted (useful for
//     handling duplicates).
//   - Binary Trie (or 0/1 Trie): a Trie over binary strings (bits),
//     used for XOR / bitwise operations.
//   - XOR (exclusive OR): a bitwise operation, often used with binary
//     Tries to find the maximum XOR between numbers.
// =====================================================================

// =====================================================================
// 1) Basic Trie for lowercase English letters (a-z)
//    This is the most common type used in string problems.
//    It supports insert, search, startsWith, and deletion.
// =====================================================================

struct TrieNode {
    // child[26] for 'a'..'z'
    // Using an array is faster and simpler than unordered_map.
    TrieNode* child[26];
    bool isEnd;          // true if a word ends at this node
    int wordCount;       // number of times this word was inserted
    int prefixCount;     // number of words that pass through this node

    TrieNode() {
        for (int i = 0; i < 26; i++) child[i] = nullptr;
        isEnd = false;
        wordCount = 0;
        prefixCount = 0;
    }
};

class Trie {
private:
    TrieNode* root;

    // Helper for deleteWord (recursive)
    bool deleteWordHelper(TrieNode* node, const string& word, int depth) {
        if (!node) return false;
        if (depth == (int)word.size()) {
            // We reached the end of the word
            if (node->isEnd) {
                node->wordCount--;
                // If wordCount becomes 0, remove the end marker
                if (node->wordCount == 0) {
                    node->isEnd = false;
                }
                return true;
            }
            return false; // word not found
        }
        int idx = word[depth] - 'a';
        bool deleted = deleteWordHelper(node->child[idx], word, depth + 1);
        if (deleted) {
            // Decrement prefix count of the child
            if (node->child[idx]) {
                node->child[idx]->prefixCount--;
                // If child has no more words and no children, delete it
                TrieNode* child = node->child[idx];
                if (child->prefixCount == 0 && !child->isEnd) {
                    bool hasChild = false;
                    for (int i = 0; i < 26; i++) {
                        if (child->child[i]) { hasChild = true; break; }
                    }
                    if (!hasChild) {
                        delete child;
                        node->child[idx] = nullptr;
                    }
                }
            }
            return true;
        }
        return false;
    }

    // Helper for getWordsWithPrefix (DFS)
    void dfsCollect(TrieNode* node, string& current, vector<string>& result) {
        if (node->isEnd) result.push_back(current);
        for (int i = 0; i < 26; i++) {
            if (node->child[i]) {
                current.push_back('a' + i);
                dfsCollect(node->child[i], current, result);
                current.pop_back();
            }
        }
    }

    // Helper for smallestWordWithPrefixLength (checks if a path of given length exists)
    bool canReachLength(TrieNode* node, int remaining) {
        if (remaining == 0) return true;
        for (int c = 0; c < 26; c++) {
            if (node->child[c] && canReachLength(node->child[c], remaining - 1)) {
                return true;
            }
        }
        return false;
    }

public:
    Trie() {
        root = new TrieNode();
    }

    // 1.1) Insert a word into the Trie.
    //      Purpose: Adds the given word to the dictionary.
    //      Input: word (string) – the word to insert.
    //      Output: none.
    //      Time Complexity: O(len(word)), where len is the length of the word.
    //      Constraints: word contains only lowercase English letters ('a'..'z').
    //      Note: If the same word is inserted multiple times, each insertion
    //            increments wordCount and prefixCount for all its nodes.
    void insert(const string& word) {
        TrieNode* cur = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!cur->child[idx]) {
                cur->child[idx] = new TrieNode();
            }
            cur = cur->child[idx];
            cur->prefixCount++;
        }
        cur->isEnd = true;
        cur->wordCount++;
    }

    // 1.2) Search for a complete word in the Trie.
    //      Purpose: Checks if the exact word exists in the Trie.
    //      Input: word (string) – the word to search.
    //      Output: returns true if the word exists (at least once), false otherwise.
    //      Time Complexity: O(len(word)).
    //      Constraints: word contains only lowercase letters.
    //      Note: This function does NOT check if the word is a prefix of a longer word;
    //            it requires isEnd to be true at the last node.
    bool search(const string& word) {
        TrieNode* cur = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!cur->child[idx]) return false;
            cur = cur->child[idx];
        }
        return cur->isEnd;
    }

    // 1.3) Check if there is any word that starts with the given prefix.
    //      Purpose: Tests whether the given prefix is stored in the Trie.
    //      Input: prefix (string) – the prefix to check.
    //      Output: returns true if at least one word has this prefix.
    //      Time Complexity: O(len(prefix)).
    //      Constraints: prefix contains only lowercase letters.
    //      Note: If the prefix itself is a complete word, it still returns true.
    bool startsWith(const string& prefix) {
        TrieNode* cur = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (!cur->child[idx]) return false;
            cur = cur->child[idx];
        }
        return true;
    }

    // 1.4) Count how many times a given word has been inserted.
    //      Purpose: Returns the frequency of a specific word (0 if never inserted).
    //      Input: word (string) – the word to count.
    //      Output: integer – number of insertions of this exact word.
    //      Time Complexity: O(len(word)).
    //      Constraints: word contains only lowercase letters.
    int countWord(const string& word) {
        TrieNode* cur = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!cur->child[idx]) return 0;
            cur = cur->child[idx];
        }
        return cur->wordCount;
    }

    // 1.5) Count how many words have the given prefix.
    //      Purpose: Returns the total number of inserted words that start
    //               with the given prefix.
    //      Input: prefix (string) – the prefix to count.
    //      Output: integer – number of words with this prefix.
    //      Time Complexity: O(len(prefix)).
    //      Constraints: prefix contains only lowercase letters.
    int countPrefix(const string& prefix) {
        TrieNode* cur = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (!cur->child[idx]) return 0;
            cur = cur->child[idx];
        }
        return cur->prefixCount;
    }

    // 1.6) Delete a word from the Trie (one occurrence).
    //      Purpose: Removes one occurrence of the given word from the Trie.
    //      Input: word (string) – the word to delete.
    //      Output: returns true if the word existed and was deleted,
    //              false otherwise.
    //      Time Complexity: O(len(word)).
    //      Constraints: word contains only lowercase letters.
    //      Note: This function uses a helper to recursively delete nodes
    //            that are no longer needed (no children and not end of another word).
    bool deleteWord(const string& word) {
        return deleteWordHelper(root, word, 0);
    }

    // =====================================================================
    // 2) Advanced: Longest Common Prefix among two strings using Trie
    //    This is a common trick: to find the longest common prefix of
    //    two strings, you can insert one string and then traverse the other.
    // =====================================================================

    // 2.1) Find the length of the longest common prefix of two strings.
    //      Purpose: Given two strings a and b, returns the length of their
    //               longest common prefix.
    //      Input: a, b (strings) – the two strings to compare.
    //      Output: integer – length of the longest common prefix.
    //      Time Complexity: O(len(a) + len(b)) if we insert a first,
    //                       but for a single comparison, it's O(min(len(a), len(b))).
    //      Constraints: strings contain lowercase letters.
    //      Note: This implementation inserts a into a temporary Trie,
    //            then traverses b until mismatch. You can reuse an existing
    //            Trie if needed.
    int longestCommonPrefixLength(const string& a, const string& b) {
        // Build a temporary Trie from a
        Trie tempTrie;
        tempTrie.insert(a);
        TrieNode* cur = tempTrie.root;
        int len = 0;
        for (char ch : b) {
            int idx = ch - 'a';
            if (!cur->child[idx]) break;
            cur = cur->child[idx];
            len++;
        }
        return len;
    }

    // =====================================================================
    // 3) Binary Trie (0/1 Trie) for Bitwise XOR problems
    //    This is a very common pattern in ECPC/ACPC.
    //    The Trie stores integers as binary strings (bits from MSB to LSB).
    //    The maximum number of bits is usually 30 or 31 (since numbers up to
    //    1e9 require 30 bits, plus sign).
    // =====================================================================

    // Binary Trie node: two children for bit 0 and bit 1.
    struct BinaryTrieNode {
        BinaryTrieNode* child[2];
        int count; // number of numbers that pass through this node
        BinaryTrieNode() {
            child[0] = child[1] = nullptr;
            count = 0;
        }
    };

    class BinaryTrie {
    private:
        BinaryTrieNode* root;
        int MAX_BITS; // usually 30 or 31 (e.g., 31 for signed int)

        // Helper for countLessThanXOR
        int countLessThanXORHelper(BinaryTrieNode* node, int x, int limit, int bit) {
            if (!node || bit < 0) return 0;
            if (limit < 0) return 0;
            int xb = (x >> bit) & 1;
            int lb = (limit >> bit) & 1;
            int res = 0;
            if (lb == 1) {
                // XOR bit 0 gives a smaller prefix: count all numbers with that bit
                if (node->child[xb]) {
                    res += node->child[xb]->count; // because XOR bit 0 < 1 at this bit
                }
                // Continue with XOR bit 1 (equal to limit's bit)
                if (node->child[xb ^ 1]) {
                    res += countLessThanXORHelper(node->child[xb ^ 1], x, limit, bit - 1);
                }
            } else {
                // limit bit is 0, so XOR bit must be 0 to stay equal
                if (node->child[xb]) {
                    res += countLessThanXORHelper(node->child[xb], x, limit, bit - 1);
                }
            }
            return res;
        }

    public:
        BinaryTrie(int maxBits = 31) {
            root = new BinaryTrieNode();
            MAX_BITS = maxBits;
        }

        // 3.1) Insert a number into the Binary Trie.
        //      Purpose: Adds the binary representation of 'num' into the Trie.
        //      Input: num (int) – the number to insert.
        //      Output: none.
        //      Time Complexity: O(MAX_BITS) (constant, ~31 steps).
        //      Constraints: num fits in a signed 32-bit integer.
        //      Note: Duplicates are allowed (count is incremented at each node).
        void insert(int num) {
            BinaryTrieNode* cur = root;
            for (int bit = MAX_BITS; bit >= 0; bit--) {
                int b = (num >> bit) & 1;
                if (!cur->child[b]) cur->child[b] = new BinaryTrieNode();
                cur = cur->child[b];
                cur->count++;
            }
        }

        // 3.2) Query the maximum XOR of 'num' with any number in the Trie.
        //      Purpose: Given a number, find the maximum XOR value you can get
        //               by XORing it with any number currently inserted.
        //      Input: num (int) – the number to XOR against.
        //      Output: int – the maximum XOR value.
        //      Time Complexity: O(MAX_BITS).
        //      Constraints: Trie is not empty.
        //      Note: This is useful for "Maximum XOR of Two Numbers in an Array".
        int maxXOR(int num) {
            BinaryTrieNode* cur = root;
            int ans = 0;
            for (int bit = MAX_BITS; bit >= 0; bit--) {
                int b = (num >> bit) & 1;
                int desired = b ^ 1; // we want the opposite bit to maximize XOR
                if (cur->child[desired]) {
                    ans |= (1 << bit);
                    cur = cur->child[desired];
                } else {
                    cur = cur->child[b];
                }
            }
            return ans;
        }

        // 3.3) Query the maximum XOR pair (with a given number) but returns the
        //      number in the Trie that gives that XOR (not just the value).
        //      Purpose: Similar to maxXOR, but returns the original number
        //               from the Trie that yields the max XOR.
        //      Input: num (int)
        //      Output: int – the number in the Trie that maximizes XOR.
        //      Time Complexity: O(MAX_BITS).
        //      Note: This assumes the Trie has at least one element.
        int maxXORNumber(int num) {
            BinaryTrieNode* cur = root;
            int ans = 0;
            for (int bit = MAX_BITS; bit >= 0; bit--) {
                int b = (num >> bit) & 1;
                int desired = b ^ 1;
                if (cur->child[desired]) {
                    ans |= (desired << bit);
                    cur = cur->child[desired];
                } else {
                    ans |= (b << bit);
                    cur = cur->child[b];
                }
            }
            return ans;
        }

        // 3.4) Count numbers in the Trie that are less than a given value
        //      after XORing with a given number.
        //      Purpose: For a fixed x, count how many y in the Trie satisfy
        //               (x ^ y) < limit. This is useful in problems like
        //               "Count pairs with XOR less than K".
        //      Input: x (int), limit (int)
        //      Output: int – count of numbers y such that (x ^ y) < limit.
        //      Time Complexity: O(MAX_BITS).
        //      Constraints: Trie is not empty; limit >= 0.
        int countLessThanXOR(int x, int limit) {
            return countLessThanXORHelper(root, x, limit, MAX_BITS);
        }
    };

    // =====================================================================
    // 4) Trie with Frequency for Autocomplete / Suggestions
    //    Not very common in ECPC but can be useful.
    // =====================================================================

    // 4.1) Get all words with a given prefix (lexicographically sorted).
    //      Purpose: Returns a list of all words that start with the given prefix.
    //      Input: prefix (string)
    //      Output: vector<string> – all words in the Trie with that prefix.
    //      Time Complexity: O(len(prefix) + number of words in the subtree).
    //      Constraints: words contain lowercase letters.
    //      Note: This can be memory heavy; use with caution.
    vector<string> getWordsWithPrefix(const string& prefix) {
        vector<string> result;
        TrieNode* cur = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (!cur->child[idx]) return result;
            cur = cur->child[idx];
        }
        string current = prefix;
        dfsCollect(cur, current, result);
        return result;
    }

    // =====================================================================
    // 5) Advanced Idea: Trie + DP for Word Break (not a direct function,
    //    but a pattern). We include a function that checks if a string
    //    can be segmented into words from the Trie.
    // =====================================================================

    // 5.1) Word Break: Check if the string can be segmented into words
    //      that exist in the Trie.
    //      Purpose: Given a string s, determine if it can be split into
    //               a sequence of dictionary words (all present in Trie).
    //      Input: s (string) – the string to segment.
    //      Output: bool – true if segmentable, false otherwise.
    //      Time Complexity: O(n^2) in worst case (DP + Trie traversal),
    //                       but can be O(n * maxLen) if we limit.
    //      Constraints: words in Trie are lowercase; s lowercase.
    //      Note: This is a classic DP problem. The Trie helps to check
    //            prefixes quickly.
    bool wordBreak(const string& s) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            if (!dp[i]) continue;
            TrieNode* cur = root;
            for (int j = i; j < n; j++) {
                int idx = s[j] - 'a';
                if (!cur->child[idx]) break;
                cur = cur->child[idx];
                if (cur->isEnd) {
                    dp[j + 1] = true;
                }
            }
        }
        return dp[n];
    }

    // =====================================================================
    // 6) Trick: Lexicographically smallest string with given prefix and
    //    length constraints (used in some ECPC problems).
    // =====================================================================

    // 6.1) Find the lexicographically smallest word of length L that
    //      starts with prefix and is present in the Trie.
    //      Purpose: Used when you need to construct the smallest string
    //               that satisfies certain prefix and length constraints.
    //      Input: prefix (string), length (int)
    //      Output: string – the smallest word, or empty if none exists.
    //      Time Complexity: O(length * 26) (DFS over Trie).
    //      Constraints: Trie must contain at least one such word.
    string smallestWordWithPrefixLength(const string& prefix, int length) {
        TrieNode* cur = root;
        string res = prefix;
        // First, traverse to the end of the prefix
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (!cur->child[idx]) return "";
            cur = cur->child[idx];
        }
        if ((int)res.size() > length) return ""; // prefix already longer
        // Greedily choose the smallest character that leads to a valid word
        while ((int)res.size() < length) {
            bool found = false;
            for (int c = 0; c < 26; c++) {
                if (cur->child[c]) {
                    // Check if this branch can reach the required length
                    if (canReachLength(cur->child[c], length - (int)res.size() - 1)) {
                        res.push_back('a' + c);
                        cur = cur->child[c];
                        found = true;
                        break;
                    }
                }
            }
            if (!found) return "";
        }
        return res;
    }

    // =====================================================================
    // 7) Aho-Corasick (Advanced) – not fully implemented, just a note.
    //    For multiple pattern matching, you can build a trie with failure
    //    links. This is a common advanced topic in ECPC/ACPC.
    //    If you need it, implement a separate class for Aho-Corasick.
    //    It is essentially a Trie with BFS failure links.
    // =====================================================================

    // =====================================================================
    // 8) Important Notes / Warnings
    //    - Always ensure the character set is consistent (e.g., lowercase).
    //    - Memory: each node has 26 pointers; for large data, it can be
    //      heavy. Use unordered_map or vector of ints (compressed trie)
    //      if memory is an issue.
    //    - For Binary Trie, MAX_BITS depends on the maximum number you
    //      will insert. Usually 30 for up to 1e9, 31 if including sign.
    //    - The wordBreak and getWordsWithPrefix functions are provided as
    //      examples of advanced usage; adjust as needed.
    //    - Deletion is tricky; our deleteWord handles one occurrence, but
    //      you may need to adjust for your use case.
    // =====================================================================
};

// =====================================================================
// Example usage (you can remove this when using as a black box)
// =====================================================================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Basic Trie
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("apricot");
    cout << boolalpha;
    cout << "search('app'): " << trie.search("app") << '\n';          // true
    cout << "search('apple'): " << trie.search("apple") << '\n';      // true
    cout << "search('ap'): " << trie.search("ap") << '\n';            // false
    cout << "startsWith('ap'): " << trie.startsWith("ap") << '\n';    // true
    cout << "countPrefix('ap'): " << trie.countPrefix("ap") << '\n';  // 3 (apple, app, apricot)
    cout << "countWord('app'): " << trie.countWord("app") << '\n';    // 1

    // Binary Trie for XOR
    Trie::BinaryTrie bt(30);
    bt.insert(5);   // 101
    bt.insert(2);   // 010
    bt.insert(7);   // 111
    cout << "maxXOR with 1: " << bt.maxXOR(1) << '\n';  // 6 (1 xor 7 = 6)
    cout << "maxXOR with 3: " << bt.maxXOR(3) << '\n';  // 4 (3 xor 7 = 4)

    // Word Break
    Trie dict;
    dict.insert("leet");
    dict.insert("code");
    cout << "wordBreak('leetcode'): " << dict.wordBreak("leetcode") << '\n'; // true
    cout << "wordBreak('leetocode'): " << dict.wordBreak("leetocode") << '\n'; // false

    // Longest common prefix
    cout << "LCP('abcdef', 'abcxyz'): " << trie.longestCommonPrefixLength("abcdef", "abcxyz") << '\n'; // 3

    return 0;
}