class Solution {
public:
    bool res = false;
    string num;
    bool isAdditiveNumber(string num) {
        this->num = num;
        if(num.size() <= 2) return false;
        for(int i = 1; i <= num.size() - 2; i ++){
            for(int j = 1; i + j < num.size(); j ++){
                string a = num.substr(0, i);
                string b = num.substr(i, j);
                if(!res && !(a.size() > 1 && a[0] == '0') && !(b.size() > 1 && b[0] == '0')) 
                    dfs(i + j - 1, a, b);
                if(res) return true;               
            }
        }
        return false;
    }
    void dfs(int idx, string& a, string& b){
        string c = ccl(a, b);
        if(idx + c.size() >= num.size()) return;
        if(idx + c.size() == num.size() - 1){
            string t = num.substr(idx + 1, c.size());
            if(c == t) res = true;
            return;
        }
        string t = num.substr(idx + 1, c.size());
        if(c == t) dfs(idx + c.size(), b, t);
    }

    string ccl(string& a, string& b){
        string aa, bb;
        if(b.size() < a.size()) aa = b, bb = a;
        else aa = a, bb = b;
        int i1 = aa.size() - 1, i2 = bb.size() - 1;
        int t = 0;
        vector<char> v;
        while(i1 >= 0 && i2 >= 0){
            int s = (aa[i1] - '0') + (bb[i2] - '0') + t;
            t = s / 10;
            auto r = (s % 10) + '0';
            v.push_back(r);
            i1 --; i2 --;
        }
        while(i2 >= 0){
            int s = (bb[i2] - '0') + t;
            t = s / 10;
            auto r = (s % 10) + '0';
            v.push_back(r);
            i2 --;
        }
        if(t) v.push_back(t + '0');
        string ans;
        for(int i = v.size() - 1; i >= 0; i --)
            ans += v[i] ;
        return ans;
    }
};

class NumMatrix {
public:
    const static int N = 210;
    int s[N][N];
    int n, m;
    NumMatrix(vector<vector<int>>& matrix) {
        n = matrix.size(), m = matrix[0].size();
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++){
                if(!i && !j) s[i][j] = matrix[i][j];
                else if(!i) s[i][j] = s[i][j - 1] + matrix[i][j];
                else if(!j) s[i][j] = s[i - 1][j] + matrix[i][j];
                else s[i][j] = s[i][j - 1] + s[i - 1][j] + matrix[i][j] - s[i - 1][j - 1];
            }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        if(!row1 && !col1) return s[row2][col2];
        else if(!row1) return s[row2][col2] - s[row2][col1 - 1];
        else if(!col1) return s[row2][col2] - s[row1 - 1][col2];
        else return s[row2][col2] - s[row2][col1 - 1] - s[row1 - 1][col2] + s[row1 - 1][col1 - 1];
    }
};

class NumArray {
public:
    const static int N = 1e5 + 11;
    int s[N];
    int n;
    NumArray(vector<int>& nums) {
        n = nums.size();
        for(int i = 0;i < n; i ++)
            if(!i) s[i] = nums[i];
            else s[i] = s[i - 1] + nums[i];
    }

    int sumRange(int left, int right) {
        if(!left) return s[right];
        else return s[right] - s[left - 1];
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    string res;
    void dfs_s(TreeNode* root){
        if(!root) res += "#,";
        else{
            res += to_string(root->val);
            res += ",";
            dfs_s(root->left);
            dfs_s(root->right);
        }
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        dfs_s(root);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int i = 0;
        return dfs_d(data, i);
    }
    TreeNode* dfs_d(string& data, int& i){
        if(data[i] == '#'){
            i += 2;
            return NULL;
        }
        else{
            int d = i;
            while(d < data.size() && data[d] != ',') d ++;
            auto root = new TreeNode(stoi(data.substr(i, d - i)));
            i = d + 1;
            if(i < data.size()) root->left = dfs_d(data, i);
            if(i < data.size()) root->right = dfs_d(data, i);
            return root;
        }
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> h1;
    priority_queue<int, vector<int>, greater<int>> h2;
    MedianFinder() {

    }

    void addNum(int num) {
        if(h1.size() && num <= h1.top()){
            h1.push(num);
            while(h1.size() - h2.size() >= 2){
                h2.push(h1.top());
                h1.pop();
            }
        }
        else{
            h2.push(num);
            while(h2.size() - h1.size() >= 2){
                h1.push(h2.top());
                h2.pop();
            }
        }
    }

    double findMedian() {
        int n = h1.size() + h2.size();
        if(n%2 == 0){
            if(h1.size() == h2.size())
                return (double)(h1.top() + h2.top()) / 2;
            else if(h1.size() > h2.size()){
                double a1 = h1.top();
                h1.pop();
                double a2 = h1.top();
                h1.push(a1);
                return (double)(a1 + a2) / 2; 
            }
            else if(h1.size() < h2.size()){
                double a1 = h2.top();
                h2.pop();
                double a2 = h2.top();
                h2.push(a1);
                return (double)(a1 + a2) / 2; 
            }
        }
        else if(h1.size() > h2.size())
            return h1.top();

        else if(h1.size() < h2.size())
            return h2.top();

        return 0;
    }
};

























/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4;
    }
};

class Solution {
public:
    unordered_map<char, string> h1;
    unordered_map<string, char> h2;
    vector<string> v;
    bool wordPattern(string pattern, string s) {
        int n1 = pattern.size(), n2 = s.size();
        for(int i = 0; i < n2; i ++){
            int j = i;
            string tmp;
            while(j < n2 && s[j] != ' ')
                tmp += s[j ++];
            v.push_back(tmp);
            i = j;
        }
        if(n1 != v.size()) return false;
        for(int i = 0;i < n1; i ++){
            char c = pattern[i];
            if(h1.count(c)){
                if(h1[c] != v[i] || h2[v[i]] != c) return false;
            }
            else if(h2.count(v[i])) return false;
            else{        
                h1[c] = v[i];
                h2[v[i]] = c;
            }
        }
        return true;
    }
};

class Solution {
public:
    int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
    int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};
    void gameOfLife(vector<vector<int>>& board) {
        int n = board.size(), m = board[0].size();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j ++){
                int cnt = 0;
                for(int k = 0; k < 8; k ++){
                    int a = i + dx[k], b = j + dy[k];
                    if(a >= 0 && a < n && b >= 0 && b < m && (board[a][b] & 1))
                        cnt ++;
                }
                if(cnt == 2 && board[i][j]) board[i][j] += 2;
                else if(cnt == 3) board[i][j] += 2;
            }

        for(int i = 0;i < n; i++)
            for(int j = 0; j < m; j ++)
                board[i][j] = board[i][j] >> 1;

    }
};

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0;i < n; i++){
            while(nums[i] != i+1 && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);
            if(nums[i] != i + 1 && nums[i] == nums[nums[i] - 1]) return nums[i];
        }
        return nums[nums.size() - 1];
    }
};

/*
 * Below is the interface for Iterator, which is already defined for you.
 * **DO NOT** modify the interface for Iterator.
 *
 *  class Iterator {
 *      struct Data;
 *      Data* data;
 *  public:
 *      Iterator(const vector<int>& nums);
 *      Iterator(const Iterator& iter);
 *
 *      // Returns the next element in the iteration.
 *      int next();
 *
 *      // Returns true if the iteration has more elements.
 *      bool hasNext() const;
 *  };
 */

class PeekingIterator : public Iterator {
public:
    int cur = -1;
    int s = 0;
    vector<int> v;
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        s = nums.size();
        v = nums;
    }

    // Returns the next element in the iteration without advancing the iterator.
    int peek() {
        return v[cur + 1];
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    int next() {
        return v[++cur];
    }

    bool hasNext() const {
        return cur < s - 1;
    }
};