void my_qsort(vector<int> &nums, int l, int r) {
    if (l >= r)
        return;

    int j = r;
    int i;
    for (i = l   1; i <= j;   i) {
        if (nums[i] > nums[l]) {
            // 这里之所以需要i--, 是不知道交换的 j 是不是比 l 大
            // 所以让 i 停在原地
            swap(nums[i--], nums[j--]);
        }
    }
    swap(nums[j], nums[l]);
    my_qsort(nums, l, j - 1);
    my_qsort(nums, j   1, r);
}

void my_qsort(vector<int> &nums, int l, int r) {
    if (l >= r)
        return;
  
    int t = l;
    int i;
    for (i = l   1; i <= r;   i) {
        if (nums[i] < nums[l])
            swap(nums[i], nums[  t]);
    }
    swap(nums[l], nums[t]);
    my_qsort(nums, l, t - 1);
    my_qsort(nums, t   1, r);
}

void merge(int *nums, int left, int right) {
    if (left >= right)
        return;

    int st1, ed1, st2, ed2;
    st1 = left;
    ed1 = left   (right - left) / 2;
    st2 = ed1   1;
    ed2 = right;
    merge(nums, st1, ed1);
    merge(nums, st2, ed2);

    int temp[right - left   1];
    int t = 0;
    while (st1 <= ed1 && st2 <= ed2)
        temp[t  ] = nums[st1] < nums[st2] ? nums[st1  ] : nums[st2  ];
    while (st1 <= ed1)
        temp[t  ] = nums[st1  ];
    while (st2 <= ed2)
        temp[t  ] = nums[st2  ];

    t = 0;
    for (int i = left; i <= right;   i)
        nums[i] = temp[t  ];
}

void merge_sort(int *nums, size_t len) {
    merge(nums, 0, len - 1);
}

void my_swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int findKthLargest(int* nums, int numsSize, int k){
    int l = 0, r = numsSize-1;

    while (1) {
        int i = l   1;
        int t = l;
        for (; i <= r;   i) {
            if (nums[i] < nums[l])
                my_swap(&nums[  t], &nums[i]);
        }
        my_swap(&nums[l], &nums[t]);
        if (t == numsSize - k)
            return nums[t];
        else if (t < numsSize - k)
            l = t   1;
        else {
            r = t - 1;
        }
    }
    return 0;
}

class Solution {
    int my_qsort(vector<int> &nums, int l, int r, int k) {
        int t = l;
        int i = l   1;
        for (; i <= r;   i) {
            if (nums[i] < nums[l]) {
                swap(nums[  t], nums[i]);
            }
        }
        swap(nums[l], nums[t]);

        if (t < nums.size() - k) {
            return my_qsort(nums, t   1, r, k);
        } else if (t > nums.size() - k) {
            return my_qsort(nums, l, t - 1, k);
        } else {
            return nums[t];
        }
    }

public:
    int findKthLargest(vector<int> &nums, int k){
        return my_qsort(nums, 0, nums.size() - 1, k);
    }
};

class Solution {
public:
    vector<int> getLeastNumbers(vector<int> &arr, int k) {
        vector<int> vec(k, 0);
        if (k == 0)
            return vec;
        priority_queue<int> Q;
        for (int i = 0; i < k;   i) {
            Q.push(arr[i]);
        }

        for (int i = k; i < arr.size();   i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k;   i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

int* exchange(int* nums, int numsSize, int* returnSize){
    int even_st, even_ed, tmp;
    *returnSize = numsSize;
    even_st = even_ed = 0;
    
    for (int i = 0; i < numsSize;   i) {
        if (nums[i] % 2) {
          tmp = nums[even_st];
          nums[even_st] = nums[i];
          nums[i] = tmp;
          even_st  ;
        }
        even_ed  ;
    }
    
    return nums;
}

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int zero_st = 0;
        for (int i = zero_st; i < nums.size();   i) {
            if (nums[i] != 0)
                swap(nums[zero_st  ], nums[i]);
        }
    }
};

class Solution {
public:
    string minNumber(vector<int> &nums) {
        string x_str, y_str;
        sort(nums.begin(), nums.end(), [&](int &x, int &y) {
            x_str = to_string(x);
            y_str = to_string(y);
            return x_str   y_str < y_str   x_str;
        });

        string res;
        for (auto num: nums) {
            res  = to_string(num);
        }
        return res;
    }
};

class Solution {
public:
    int merge(vector<int> &nums, int left, int right) {
        if (left >= right)
            return 0;

        int st1, ed1, st2, ed2;
        st1 = left;
        ed1 = left   (right - left) / 2;
        st2 = ed1   1;
        ed2 = right;
        int count  = merge(nums, st1, ed1)   merge(nums, st2, ed2);

        vector<int> temp(right - left   1);
        int t = 0;
        while (st1 <= ed1 && st2 <= ed2)
            temp[t  ] = nums[st2] < nums[st1] ? ({
                count  = ed1 - st1   1;
                nums[st2  ];
            }) : nums[st1  ];
        while (st1 <= ed1)
            temp[t  ] = nums[st1  ];
        while (st2 <= ed2)
            temp[t  ] = nums[st2  ];

        t = 0;
        for (int i = left; i <= right;   i)
            nums[i] = temp[t  ];
        
        return count;
    }

    int reversePairs(vector<int> &nums) {
        return merge(nums, 0, nums.size() - 1);
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res({intervals[0]});

        for (auto interval: intervals) {
            if (interval[0] > res.back()[1])
                res.push_back(interval);
            else
                res.back()[1] = max(res.back()[1], interval[1]);
        }
        
        return res;
    }
};

class Solution {
    unordered_set<int> set;
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0)
            return 0;

        for (auto num : nums) {
            set.insert(num);
        }

        int ans = 1;
        for (auto num : nums) {
            if (set.count(num - 1))
                continue;
            
            int cur = 1;
            while (set.count(  num))
               ans = max(  cur, ans);
        }

        return ans;
    }
};

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> que_min;
    priority_queue<int, vector<int>, greater<int>> que_max;
    MedianFinder() = default;

    void addNum(int num) {
        if (que_min.empty() || num <= que_min.top()) {
            que_min.push(num);
            if (que_max.size()   1 < que_min.size()) {
                que_max.push(que_min.top());
                que_min.pop();
            }
        } else {
            que_max.push(num);
            if (que_max.size() > que_min.size()) {
                que_min.push(que_max.top());
                que_max.pop();
            }
        }
    }

    double findMedian() {
        if (que_min.size() > que_max.size())
            return que_min.top();
        else
            return (que_min.top()   que_max.top()) / 2.;
    }
};

int findMin(int* nums, int numsSize) {
    int low = 0;
    int high = numsSize - 1;
    while (low < high) {
        int pivot = low   (high - low) / 2;
        if (nums[pivot] < nums[high]) {	// 兼顾两者, 所以和大的比较
            high = pivot;
        } else {
            low = pivot   1;
        }
    }
    return nums[low];
}

int findMin(int* nums, int numsSize) {
    int low = 0;
    int high = numsSize - 1;
    while (low < high) {
        int pivot = low   (high - low) / 2;
        if (nums[pivot] < nums[high]) {
            high = pivot;
        } else if (nums[pivot] > nums[high]) {
            low = pivot   1;
        } else {	// 相等
            high -= 1;
        }
    }
    return nums[low];
}

class Solution {
public:
    int search(vector<int> &nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        int m;

        if (r == -1)
            return -1;
        if (r == 0)
            return nums[l] == target ? l : -1;

        while (l <= r) {
            m = l   (r - l) / 2;
            if (target == nums[m])
                return m;

            if (nums[l] <= nums[m]) {
                if (nums[l] <= target && target < nums[m]) {
                    r = m - 1;
                } else {
                    l = m   1;
                }
            } else {
                if (nums[m] < target && target <= nums[r]) {
                    l = m   1;
                } else {
                    r = m - 1;
                }
            }
        }

        return -1;
    }
};

class Solution {
public:
    int binarySearch(vector<int> &nums, int target, bool lower) {
        int left = 0;
        int right = nums.size() - 1
        int ans = nums.size();
      
        while (left <= right) {
            int mid = (left   right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid   1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int> &nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
            return vector<int>{leftIdx, rightIdx};
        }
        return vector<int>{-1, -1};
    }
};

class Solution {
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况
            if (index1 == m) {
                return nums2[index2   k - 1];
            }
            if (index2 == n) {
                return nums1[index1   k - 1];
            }
            if (k == 1) {
                return min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int newIndex1 = min(index1   k / 2 - 1, m - 1);
            int newIndex2 = min(index2   k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1   1;
                index1 = newIndex1   1;
            }
            else {
                k -= newIndex2 - index2   1;
                index2 = newIndex2   1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size()   nums2.size();
        if (totalLength % 2 == 1) {
            return getKthElement(nums1, nums2, (totalLength   1) / 2);
        }
        else {
            return (getKthElement(nums1, nums2, totalLength / 2)   getKthElement(nums1, nums2, totalLength / 2   1)) / 2.0;
        }
    }
};

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x; 
        int ret = 0;
        while (l <= r) {
            int m = l   (r - l) / 2;
            if ((long) m * m <= x) {
                ret = m;
                l = m   1;
            } else {
                r = m - 1;
            }
        }
        
        return ret;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int l = 0, r = row * col - 1;
        int m, t;
        while (l <= r) {
            m = l   (r - l) / 2;
            t = matrix[m/col][m%col];
            if (t == target)
                return true;
            else if (t > target)
                r = m - 1;
            else
                l = m   1;
        }
        
        return false;
    }
};

char firstUniqChar(char *s) {
    int len = strlen(s);
    if (len == 0)
        return ' ';
    if (len == 1)
        return s[0];
    int map[26];
    memset(map, 0, sizeof(map));

    for (int i = 0; i < len; i  )
        map[s[i] - 'a']  ;
    for (int i = 0; i < len; i  )
        if (map[s[i] - 'a'] == 1)
            return s[i];
    return ' ';
}

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> map;
        for (auto &str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            map[key].emplace_back(str);
        }
        
        vector<vector<string>> ans;
        for (auto item: map) {
            ans.emplace_back(item.second);
        }
        return ans;
    }
};

void recur(struct TreeNode *cur, int *res, int *returnSize) {
    if (!cur)
        return;

    res[(*returnSize)  ] = cur->val;
    recur(cur->left, res, returnSize);
    recur(cur->right, res, returnSize);
}

int *preorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    recur(root, res, returnSize);
    return res;
}

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode *> stk;

        while (root || !stk.empty()) {
            while (root) {
                res.push_back(root->val);
                stk.push(root);
                root = root->left;
            }

            root = stk.top();
            stk.pop();
            root = root->right;
        }

        return res;
    }
};

void inorder(struct TreeNode* root, int* res, int* resSize) {
    if (!root) {
        return;
    }
    inorder(root->left, res, resSize);
    res[(*resSize)  ] = root->val;
    inorder(root->right, res, resSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = (int *) malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode *> stk;

        while (root || !stk.empty()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }

            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }

        return res;
    }
};

void postorder(struct TreeNode *root, int *res, int *resSize) {
    if (root == NULL) {
        return;
    }
    postorder(root->left, res, resSize);
    postorder(root->right, res, resSize);
    res[(*resSize)  ] = root->val;
}

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 2001);
    *returnSize = 0;
    postorder(root, res, returnSize);
    return res;
}

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode *> stk;
        TreeNode *prev = nullptr;

        while (root || !stk.empty()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }

            root = stk.top();
            if (root->right && root->right != prev) {
                root = root->right;
                continue;
            }

            stk.pop();
            res.push_back(root->val);
            prev = root;
            root = nullptr;
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        vector<vector<int>> res;
        if (!root)
            return res;

        queue<TreeNode *> q({root});
        TreeNode *cur_node;
        while (!q.empty()) {
            int cur_level_size = q.size();
            res.push_back(vector<int>());
            for (int i = 0; i < cur_level_size;   i) {
                cur_node = q.front();
                q.pop();
                res.back().push_back(cur_node->val);
                if (cur_node->left)
                    q.push(cur_node->left);
                if (cur_node->right)
                    q.push(cur_node->right);
            }
        }

        return res;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        vector<vector<int>> res;
        if (!root)
            return res;

        queue<TreeNode *> q({root});
        TreeNode *cur_node;
        while (!q.empty()) {
            int cur_level_size = q.size();
            res.push_back(vector<int>());
            for (int i = 0; i < cur_level_size;   i) {    // 遍历当前层的 size
                cur_node = q.front();
                q.pop();
                res.back().push_back(cur_node->val);
                if (cur_node->left)
                    q.push(cur_node->left);
                if (cur_node->right)
                    q.push(cur_node->right);
            }
        }

        return res;
    }
};

bool same(struct TreeNode *a, struct TreeNode *b) {
    if (b == NULL)        // b 为空可以
        return true;
    if (a == NULL)        // a 为空, b不为空不可以
        return false;

    if (a->val != b->val)
        return false;

    return same(a->left, b->left) && same(a->right, b->right);
}

bool isSubStructure(struct TreeNode *A, struct TreeNode *B) {
    if (A == NULL || B == NULL)
        return false;
    if (same(A, B))
        return true;

    return isSubStructure(A->left, B) || isSubStructure(A->right, B);
}

struct TreeNode *mirrorTree(struct TreeNode *root) {
    if (!root)
        return NULL;

    struct TreeNode *tmp = root->right;    // root-right 及其下面的子节点被存下来了
    root->right = mirrorTree(root->left);    // root-right 改变了
    root->left = mirrorTree(tmp);

    return root;
}

struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

class Solution {
private:
    bool helper(TreeNode *bt1, TreeNode *bt2) {
        if (!(bt1 || bt2))
            return true;
        if (!(bt1 && bt2))
            return false;
        if (bt1->val != bt2->val)
            return false;

        return helper(bt1->left, bt2->right) && helper(bt1->right, bt2->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        return helper(root->left, root->right);
    }
};

class Solution {
public:
    Node *treeToDoublyList(Node *root) {
        if (!root)
            return nullptr;

        dfs(root);
        head->left = pre;
        pre->right = head;

        return head;
    }

private:
    Node *pre, *head;

    void dfs(Node *cur) {
        if (!cur)
            return;

        dfs(cur->left);
        if (pre)
            pre->right = cur;
        else
            head = cur;

        cur->left = pre;
        pre = cur;

        dfs(cur->right);
    }
};

class Solution {
public:
    Node *treeToDoublyList(Node *root) {
        if (!root)
            return nullptr;
        stack<Node *> stk;
        vector<Node *> arr;

        while (root || !stk.empty()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            arr.push_back(root);
            root = root->right;
        }

        // 迭代是需要把结果存入数组, 不然遍历会出现问题
        int p, n;
        for (int i = 0; i < arr.size();   i) {
            n = (i   1) % arr.size();
            p = (i   arr.size() - 1) % arr.size();
            arr[i]->left = arr[p];
            arr[i]->right = arr[n];
        }
        return arr[0];
    }
};

class Solution {
public:
    int kthLargest(TreeNode *root, int k) {
        return helper(root, k)->val;
    }

    TreeNode *helper(TreeNode *root, int &k) {
        if (!root)
            return nullptr;

        TreeNode *tmp;
        tmp = helper(root->right, k);
        if (tmp)
            return tmp;

        if (!--k)
            return root;

        tmp = helper(root->left, k);
        if (tmp)
            return tmp;

        return nullptr;
    }
};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root)
            return 0;
        
        return 1   max(maxDepth(root->left), maxDepth(root->right));
    }
};

int max_depth(struct TreeNode *root) {
    if (!root)
        return 0;

    int l = max_depth(root->left);
    int r = max_depth(root->right);
    if (l == -1 || r == -1 || abs(l - r) > 1)
        return -1;

    return (l > r ? l : r)   1;
}

bool isBalanced(struct TreeNode* root){
   return max_depth(root) >= 0;
}

struct TreeNode *lowestCommonAncestor(struct TreeNode *root, struct TreeNode *p, struct TreeNode *q) {
    while (root) {
        if (root->val > p->val && root->val > q->val) {
            root = root->left;
            continue;
        }
        if (root->val < p->val && root->val < q->val) {
            root = root->right;
            continue;
        }

        return root;
    }
    return root;
}

struct TreeNode *lowestCommonAncestor(struct TreeNode *root, struct TreeNode *p, struct TreeNode *q) {
    if (!root || root == p || root == q)
        return root;
    
    struct TreeNode *l = lowestCommonAncestor(root->left, p, q);
    struct TreeNode *r = lowestCommonAncestor(root->right, p, q);
    if (l && r)
        return root;
    
    return l ? l : r;
}

class Solution {
private:
    bool helper(TreeNode *root, long long lower, long long upper) {
        if (root == nullptr)
            return true;

        if (root->val <= lower || root->val >= upper)
            return false;

        return helper(root->left, lower, root->val) && helper(root->right, root->val, upper);
    }
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

class Solution {
private:
    unordered_map<int, int> inorder_map;
public:
    TreeNode *buildTree(vector<int> preorder, vector<int> inorder, int pre_st, int pre_ed, int in_st, int in_ed) {
        if (pre_st > pre_ed)
            return nullptr;

        TreeNode *root = new TreeNode(preorder[pre_st]);
        int mid_index = inorder_map[preorder[pre_st]];
        int left_size = mid_index - in_st;
        root->left = buildTree(preorder, inorder, pre_st   1, pre_st   left_size, in_st, mid_index - 1);
        root->right = buildTree(preorder, inorder, pre_st   left_size   1, pre_ed, mid_index   1, in_ed);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size();   i) {
            inorder_map[inorder[i]] = i;
        }

        return buildTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};

class Solution {
private:
    unordered_map<int, int> inorder_map;
public:
    TreeNode *buildTree(vector<int> postorder, vector<int> inorder, int post_left, int post_right, int in_left, int in_right) {
        if (post_left > post_right)
            return nullptr;

        TreeNode *root = new TreeNode(postorder[post_right]);
        int mid_index = inorder_map[postorder[post_right]];
        int left_size = mid_index - in_left;
        root->left = buildTree(postorder, inorder, post_left , post_left   left_size - 1, in_left, mid_index - 1);
        root->right = buildTree(postorder, inorder, post_left   left_size, post_right - 1, mid_index   1, in_right);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size();   i) {
            inorder_map[inorder[i]] = i;
        }

        return (postorder, inorder, 0, postorder.size() - 1, 0, inorder.size() - 1);
    }
};

class Solution {
public:
    int m_res = INT_MIN;
    int helper(TreeNode *root) {
        if (!root)
            return 0;
        int left = helper(root->left);
        int right = helper(root->right);
        m_res = max({left   root->val,right   root->val, root->val, left   right   root->val, m_res});
        return max({left   root->val, right   root->val, root->val});
    }

    int maxPathSum(TreeNode *root) {
        helper(root);
        return m_res;
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for (int i = 1; i < m;   i) {
            for (int j = 1; j < n;   j) {
                dp[i][j] = dp[i - 1][j]   dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
};

class Solution {
public:
    int minPathSum(vector<vector<int>> &grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<int>> dp(row, vector<int>(col));

        dp[0][0] = grid[0][0];
        for (int i = 1; i < row;   i)
            dp[i][0] = dp[i - 1][0]   grid[i][0];

        for (int i = 1; i < col;   i)
            dp[0][i] = dp[0][i - 1]   grid[0][i];

        for (int i = 1; i < row;   i)
            for (int j = 1; j < col;   j)
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])   grid[i][j];

        return dp[row - 1][col - 1];
    }
};

int my_max(int a, int b) {
    return a > b ? a : b;
}

int maxValue(int **grid, int gridSize, int *gridColSize) {
    if (gridSize == 0)
        return 0;
    for (int i = 1; i < gridSize;   i)
        grid[i][0]  = grid[i - 1][0];

    for (int i = 1; i < gridColSize[0];   i)
        grid[0][i]  = grid[0][i - 1];

    for (int i = 1; i < gridSize;   i) {
        for (int j = 1; j < gridColSize[i];   j) {
            grid[i][j] = my_max(grid[i][j]   grid[i - 1][j], grid[i][j]   grid[i][j - 1]);
        }
    }

    return grid[gridSize - 1][gridColSize[0] - 1];
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur_max = nums[0];
        int res = cur_max;

        for (int i = 1; i < nums.size();   i) {
            cur_max = max(cur_max   nums[i], nums[i]);
            res = max(cur_max, res);
        }

        return res;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans;
        int hold = prices[0];

        for (int i = 1; i < prices.size();   i) {
            int benefit = prices[i] - hold;
            if (benefit < 0)
                hold = prices[i];
            else
                ans = max(ans, benefit);
        }

        return ans;
    }
};

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        int res = INT32_MIN;
        int cur_max = 0;
        for (auto &num: nums) {
            cur_max = cur_max   num > num ? cur_max   num : num;
            res = res > cur_max ? res : cur_max;
        }
        return res;
    }
};

int maxSubArray(int *nums, int numsSize) {
    if (numsSize == 0)
        return 0;

    int cur_max = nums[0];
    int pre_sum = nums[0];
    for (int i = 1; i < numsSize;   i) {
        pre_sum  = nums[i];
        if (nums[i] > pre_sum) {
            pre_sum = nums[i];
        }
        cur_max = cur_max > pre_sum ? cur_max : pre_sum;
    }

    return cur_max;
}

// 递归
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0)
            return {""};

        vector<string> ans;
        for (int i = 0; i < n;   i)
            for (string p : this->generateParenthesis(i))
                for (string q : this->generateParenthesis(n - 1 - i))
                    ans.push_back("("   p   ")"   q);
        
        return ans;
    }
};

// 迭代
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0)
            return vector<string>();

        vector<vector<string>> dp(n   1);
        dp[0] = {""};
        dp[1] = {"()"};
        for (int i = 2; i <= n;   i) {
            vector<string> cur;
            for (int j = 0; j < i;   j) {
                for (string p : dp[j]) {
                    for (string q: dp[i - j - 1]) {
                        string s = "("   p   ")"   q;
                        dp[i].push_back(s);
                    }
                }
            }
        }
        
        return dp[n];
    }
};

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()   1, vector<int>(word2.size()   1));
        for (int i = 1; i <= word1.size();   i)
            dp[i][0] = i;
        for (int i = 1; i <= word2.size();   i)
            dp[0][i] = i;

        for (int i = 0; i < word1.size();   i) {
            for (int j = 0; j < word2.size();   j) {
                if (word1[i] == word2[j])
                    dp[i 1][j 1] = dp[i][j];
                else
                    dp[i 1][j 1] = min({dp[i 1][j], dp[i][j 1], dp[i][j]})   1;
            }
        }
        
        return dp[word1.size()][word2.size()];
    }
};

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n   1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n   1;   i) {
            for (int j = 0; j < i;   j) {
                dp[i]  = dp[j] * dp[i - j - 1];
            }
        }

        return dp[n];
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set;
        for (int i = 0; i < wordDict.size();   i) {
            set.insert(wordDict[i]);
        }

        vector<bool> dp(s.size()   1);
        dp[0] = true;

        for (int i = 1; i <= s.size();   i) {
            for (int j = 0; j < i;   j) {
                if (dp[j] && set.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.size()];
    }
};

class Solution {
public:
    int rob(vector<int>& nums) {
        int pre = 0, cur = 0;
        int temp;
        for (auto num : nums) {
            if (num   pre > cur) {
                temp = pre;
                pre = cur;
                cur = num   temp;
            } else {
                pre = cur;
            }
        }

        return cur;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        vector<int> dp(n, 1);
        
        for (int i = 0; i < nums.size();   i) {
            for (int j = 0; j < i;   j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j]   1);
                }
            }
            
            res = max(dp[i], res);
        }

        return res;
    }
};

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount   1, -1);
        dp[0] = 0;
        
        for (int i = 1; i <= amount;   i) {
            int cur = INT_MAX;
            for (auto coin : coins) {
                int idx = i - coin;
                if (idx >= 0 && dp[idx] != -1) {
                    cur = min(dp[idx]   1, cur);
                }
            }
            dp[i] = cur != INT_MAX ? cur : dp[i];
        }

        return dp.back();
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2)
            return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int maxNum = *max_element(nums.begin(), nums.end());
        if (sum & 1) // odd
            return false;

        int target = sum / 2;
        if (maxNum > target)
            return false;

        vector<vector<bool>> dp(n, vector<bool>(target   1));
        for (int i = 0; i < n;   i) {
            dp[i][0] = true;
        }

        dp[0][nums[0]] = true;
        for (int i = 1; i < n;   i) {
            int num = nums[i];
            for (int j = 1; j <= target;   j) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n - 1][target];
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *last = nullptr;
        ListNode *cur = nullptr;
        while (head) {
            cur = head;
            head = head->next;
            cur->next = last;
            last = cur;
        }
        
        return cur;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head)
            return nullptr;
        
        ListNode *pre = new ListNode(0, head);
        ListNode *cur = head;
        ListNode *next;
        while ((next = cur->next)) {
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }

        return pre->next;
    }
};

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *dummy = new ListNode(0, head);
        ListNode *pre = dummy;

        for (int i = 0; i < left - 1;   i)
            pre = pre->next;

        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left;   i) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }

        return dummy->next;
    }
};

class Solution {
private:
    ListNode *reverse(ListNode *head) {
        ListNode *temp, *prev = nullptr;
        while (head) {
            temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }

        return prev;
    }

public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (!head)
            return head;

        ListNode *cur = head;
        for (int i = 1; i != k && cur;   i) {
            cur = cur->next;
        }
        if (!cur)
            return head;

        ListNode *next = cur->next;
        cur->next = nullptr;
        ListNode *reversed_head = reverse(head);
        head->next = reverseKGroup(next, k);
        return reversed_head;
    }
};

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummy = new ListNode(0, head);
        ListNode *pre = dummy;
        while (head) {
            if (head->val != val) {
                pre->next = head;
                pre = head;
            }
            head = head->next;
        }

        pre->next = nullptr;
        return dummy->next;
    }
};

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head)
            return head;

        ListNode *cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val)
                cur->next = cur->next->next;
            else
                cur = cur->next;
        }

        return head;
    }
};

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head)
            return head;

        struct ListNode *node;
        struct ListNode *cursor = head;
        struct ListNode *dummy = new ListNode;
        struct ListNode *vertex = dummy;

        while ((node = cursor) != nullptr) {
            cursor = cursor->next;
            if (cursor && node->val == cursor->val) {
                do {
                    cursor = cursor->next;
                } while (cursor && cursor->val == node->val);

                continue;
            }

            dummy->next = node;
            dummy = dummy->next;
        }
        dummy->next = nullptr;
        return vertex->next;
    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head)
            return false;
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next) {
            if (slow == fast)
                return true;

            slow = slow->next;
            fast = fast->next->next;
        }

        return false;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head)
            return head;
        
        struct ListNode *slow = head;
        struct ListNode *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                fast = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }

        }

        return nullptr;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head)
            return head;
      
        ListNode *slow, *fast;
        slow = head;
        fast = head->next;
        while (fast && fast->next) {
            if (slow == fast) {
                fast = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
            slow = slow->next;
            fast = fast->next->next;
        }

        return nullptr;
    }
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head)
            return head;
        int total_len;
        ListNode *cur = head;
        for (total_len = 1; cur->next != nullptr;   total_len, cur = cur->next);
        cur->next = head;

        k = total_len - k % total_len;
        ListNode *prev;
        for (int i = 0; i < k;   i) {
            prev = head;
            head = head->next;
        }
        
        prev->next = nullptr;
        return head;
    }
};

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head, *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!(head && head->next))
            return head;

        ListNode *vertex = head->next;
        head->next = swapPairs(vertex->next);
        vertex->next = head;
        
        return vertex;
    }
};

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head)
            return nullptr;
        ListNode *odd = head;
        ListNode *even = head->next;
        ListNode *anchor = even;
        while (even && even->next) {
            odd = odd->next = odd->next->next;
            even = even->next = even->next->next;
        }

        odd->next = anchor;
        return head;
    }
};

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *vertex = new ListNode;
        ListNode *cur = vertex;
        ListNode *temp;
        int carry = 0;
        int sum, val;

        while (l1 || l2) {
            if (l1 && l2) {
                sum = l1->val   l2->val   carry;
                l1 = l1->next;
                l2 = l2->next;
            } else if (l1) {
                sum = l1->val   carry;
                l1 = l1->next;
            } else {
                sum = l2->val   carry;
                l2 = l2->next;
            }

            val = sum % 10;
            carry = sum / 10;
            temp = new ListNode(val);
            cur->next = temp;
            cur = cur->next;
        }

        if (carry)
            cur->next = new ListNode(1);
        
        return vertex->next;
    }
};

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        stack<ListNode *> s1, s2;

        while (l1) {
            s1.push(l1);
            l1 = l1->next;
        }

        while (l2) {
            s2.push(l2);
            l2 = l2->next;
        }

        int sum, val;
        int carry = 0;
        ListNode *next = nullptr;
        ListNode *cur;
        while (!(s1.empty() && s2.empty())) {
            if (!s1.empty() && !s2.empty()) {
                sum = s1.top()->val   s2.top()->val   carry;
                s1.pop(), s2.pop();
            } else if (!s1.empty()) {
                sum = s1.top()->val   carry;
                s1.pop();
            } else {
                sum = s2.top()->val   carry;
                s2.pop();
            }
            
            val = sum % 10;
            carry = sum / 10;
            cur = new ListNode(val, next);
            next = cur;
        }
        
        if (carry)
            cur = new ListNode(1, next);
        
        return cur;
    }
};

struct ListNode *getKthFromEnd(struct ListNode *head, int k) {
    struct ListNode *slow;
    struct ListNode *fast = head;
    for (int i = 0; i < k;   i) {
        fast = fast->next;
    }
    slow = head;
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode node;
    struct ListNode *dummy = &node;
    struct ListNode *cursor = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cursor->next = l1;
            l1 = l1->next;
        } else {
            cursor->next = l2;
            l2 = l2->next;
        }
        cursor = cursor->next;
    }
    cursor->next = l1 ? l1 : l2;
    return dummy->next;
}

class Solution {
private:
    ListNode *merge_two(ListNode *headA, ListNode *headB) {
        ListNode *dummy = new ListNode;
        ListNode *cursor = dummy;
        while (headA && headB) {
            if (headA->val < headB->val) {
                cursor->next = headA;
                headA = headA->next;
            } else {
                cursor->next = headB;
                headB = headB->next;
            }

            cursor = cursor->next;
        }
        cursor->next = headA ? headA : headB;
        return dummy->next;
    }

    ListNode *merge_lists(vector<ListNode *> &lists, int l, int r) {
        if (l == r)
            return lists[l];
        if (l > r)
            return nullptr;
        int m = l   (r - l) / 2;
        return merge_two(merge_lists(lists, l, m), merge_lists(lists, m   1, r));
    }

public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return merge_lists(lists, 0, lists.size() - 1);
    }
};

class Solution {
private:
    ListNode *merge_two(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode;
        ListNode *cur = dummy;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }

        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }

public:
    ListNode *sortList(ListNode *head) {
        if (!head || !head->next)
            return head;

        ListNode *slow = head;
        ListNode *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;

        return merge_two(sortList(head), sortList(fast));
    }
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *fixA = headA;
    struct ListNode *fixB = headB;
    int flag = 0;
    while (headA != headB) {
        headA = headA ? headA->next : ({flag  ; fixB;});
        headB = headB ? headB->next : ({flag  ; fixA;});
        if (flag > 2)
            return NULL;
    }
    return headA;
}

class Solution {
private:
    ListNode *reverse_listnode(ListNode *head) {
        ListNode *temp;
        ListNode *prev = nullptr;
        while (head) {
            temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }
        
        return prev;
    }
    
    bool compare_listnode(ListNode *l1, ListNode *l2) {
        while (l2) {
            if (l1->val != l2->val)
                return false;
            l1 = l1->next;
            l2 = l2->next;
        }

        return true;
    }

public:
    bool isPalindrome(ListNode *head) {
        if (!head)
            return head;
        ListNode *slow, *fast;
        slow = fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        fast = reverse_listnode(slow);
        return compare_listnode(head, fast);
    }
};

class Solution {
private:
    ListNode *reverse_listnode(ListNode *head) {
        ListNode *temp;
        ListNode *prev = nullptr;
        while (head) {
            temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }

        return prev;
    }

    ListNode *find_median(ListNode *l1, ListNode *l2) {
        struct ListNode *slow, *fast;
        slow = fast = l1;
        while (fast != l2 && fast->next != l2) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }

    void merge(ListNode *l1, ListNode *l2) {
        ListNode *prev = new ListNode;
        ListNode *temp;
        while (l1 && l2) {
            temp = l1->next;
            prev->next = l1;
            l1->next = l2;
            prev = l2;
            l2 = l2->next;
            l1 = temp;
        }
      
      	// 注意这一行代码, 我们找中间节点没有置下一个为nullptr
      	// 所以如果是偶数节点, 最后会变成 head_list->mid_first<-mid_second
      	//																				|
      	//																				v
      	// 																				nullptr											
        if (prev == prev->next)
            prev->next = nullptr;
    }

public:
    void reorderList(ListNode *head) {
        ListNode *mid = find_median(head, nullptr);
        mid = reverse_listnode(mid);
        merge(head, mid);
    }
};

class Solution {
public:
    Node *flatten(Node *head) {
        Node *cur = head;
        stack<Node *> stk;

        while (cur) {
            if (cur->child) {
                if (cur->next) {
                    stk.push(cur->next);
                    cur->next->prev = nullptr;
                }
                cur->next = cur->child;
                cur->child->prev = cur;
                cur->child = nullptr;
            }

            if (!(cur->next || stk.empty())) {
                cur->next = stk.top();
                stk.top()->prev = cur;
                stk.pop();
            }
            cur = cur->next;
        }

        return head;
    }
};

class Solution {
public:
    void flatten(TreeNode *root) {
        if (!root)
            return;

        struct TreeNode *cur = root;
        struct TreeNode *restore_right;
        struct TreeNode *anchor;
        while (cur) {
            restore_right = cur->right;
            cur->right = cur->left;
            cur->left = nullptr;
          	anchor = cur;
            while (cur->right) {
                cur = cur->right;
            }
            cur->right = restore_right;
            cur = anchor->right;
        }
    }
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *sm_fix = new ListNode;
        ListNode *lg_fix = new ListNode;
        ListNode *sm_cur = sm_fix;
        ListNode *lg_cur = lg_fix;

        while (head) {
            if (head->val < x) {
                sm_cur->next = head;
                sm_cur = sm_cur->next;
            } else {
                lg_cur->next = head;
                lg_cur = lg_cur->next;
            }            
            head = head->next;
        }
        
        sm_cur->next = lg_fix->next;
        lg_cur->next = nullptr;
        return sm_fix->next;
    }
};

class Solution {
public:
    bool check(vector<vector<char>> &board, vector<vector<int>> &visited, int i, int j, string &s, int k) {
        if (board[i][j] != s[k])
            return false;

        // s[k] equals current board[i][j]
        if (k == s.length() - 1)
            return true;
        visited[i][j] = true;
        vector<pair<int, int>> directions{{0,  1},
                                          {0,  -1},
                                          {1,  0},
                                          {-1, 0}};
        bool result = false;
        for (auto &dir: directions) {
            int newi = i   dir.first, newj = j   dir.second;
            if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
                if (visited[newi][newj])
                    continue;
                if ((result = check(board, visited, newi, newj, s, k   1)))
                    break;
            }
        }
        visited[i][j] = false;
        return result;
    }

    bool exist(vector<vector<char>> &board, string word) {
        int h = board.size(), w = board[0].size();
        vector<vector<int>> visited(h, vector<int>(w));
        for (int i = 0; i < h;   i) {
            for (int j = 0; j < w;   j) {
                if (check(board, visited, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }
};

class Solution {
public:
    vector<vector<int>> res;

    vector<vector<int>> pathSum(TreeNode *root, int target) {
        vector<int> tmp;
        if (!root)
            return res;

        helper(root, tmp, target);
        return res;
    }

private:
    int sum_of_eles(vector<int> &arr) {
        int res = 0;
        for (int x: arr) {
            res  = x;
        }
        return res;
    }

    void helper(TreeNode *root, vector<int> &cur_arr, int target) {
        cur_arr.push_back(root->val);
        if (!root->left && !root->right) {
            if (sum_of_eles(cur_arr) == target) {
                res.push_back(cur_arr);
            }
            cur_arr.pop_back();
            return;
        }
        if (root->left)
            helper(root->left, cur_arr, target);
        if (root->right)
            helper(root->right, cur_arr, target);
        cur_arr.pop_back();
    }
};

class Solution {
public:
    int dfs(TreeNode *root, int target) {
        if (!root)
            return 0;

        int res = 0;
        if (root->val == target)
            res  ;
        res  = dfs(root->left, target - root->val);
        res  = dfs(root->right, target - root->val);
        
        return res;
    }

    int pathSum(TreeNode *root, int targetSum) {
        if (!root)
            return 0;
        return dfs(root, targetSum)   pathSum(root->left, targetSum)   pathSum(root->right, targetSum);
    }
};

class Solution {
public:
    unordered_map<int, int> map;
    int dfs(TreeNode *root, int cur_sum, int target) {
        if (!root)
            return 0;

        cur_sum  = root->val;
        int count = map.count(cur_sum - target) ? map[cur_sum - target] : 0;
        
        map[cur_sum]  ;
        count  = dfs(root->left, cur_sum, target)   dfs(root->right, cur_sum, target);
        map[cur_sum]--;
        
        return count;
    }

    int pathSum(TreeNode* root, int targetSum) {
        map[0] = 1;
        return dfs(root, 0, targetSum);
    }
};

class Solution {
private:
    vector<vector<int>> res;

    void backtrace(vector<int> &nums, int st) {
        if (st == nums.size() - 1)
            res.push_back(nums);

        for (int i = st; i < nums.size();   i) {
            swap(nums[st], nums[i]);
            backtrace(nums, st   1);
            swap(nums[i], nums[st]);
        }
    }

public:
    vector<vector<int>> permute(vector<int> &nums) {
        backtrace(nums, 0);
        return res;
    }
};

class Solution {
private:
    vector<string> res;

    void backtrack(string &s, int x) {
        if (x == s.size() - 1) {
            res.push_back(s);
            return;
        }

        set<char> st;
        for (int i = x; i < s.size();   i) {
            if (st.find(s[i]) != st.end())
                continue;
            st.insert(s[i]);
            swap(s[i], s[x]);
            backtrack(s, x   1);
            swap(s[i], s[x]);
        }
    }

public:
    vector<string> permutation(string s) {
        backtrack(s, 0);
        return res;
    }
};

class Solution {
private:
    vector<vector<int>> res;

    bool nextPermutation(vector<int> &nums) {
        int i, j;

        for (i = nums.size() - 2; i >= 0 && nums[i] >= nums[i   1]; --i);
        if (i < 0)
            return false;

        for (j = nums.size() - 1; j >= 0 && nums[i] >= nums[j]; --j);

        swap(nums[i], nums[j]);
        reverse(nums.begin()   i   1, nums.end());
        return true;
    }

public:
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        do
            res.push_back(nums);
        while (nextPermutation(nums));

        return res;
    }
};

class Solution {
public:
    void Combination(vector<char> &nums) {
        vector<vector<string>> dp(nums.size());
        dp[0].push_back(string(1, nums[0]));

        for (int i = 1; i < nums.size();   i) {
            for (int j = i - 1; j >= 0; --j) {
                for (const auto &temp: dp[j]) {
                    dp[j   1].push_back(temp   nums[i]);
                }
            }
            dp[0].push_back(string(1, nums[i]));
        }

        for (const auto& vs: dp) {
            for (const auto& str: vs) {
                cout << str << endl;
            }
        }
    }
};

class Solution {
public:
    void Combination(vector<char> &nums) {
        vector<vector<string>> dp(nums.size()   1);
        dp[0].push_back("");

        for (int i = 0; i < nums.size();   i) {
            for (int j = i; j >= 0; --j) {
                for (const auto &temp: dp[j]) {
                    dp[j   1].push_back(temp   nums[i]);
                }
            }
        }

        for (const auto& vs: dp) {
            for (const auto& str: vs) {
                cout << str << endl;
            }
        }
    }
};

class Solution {
public:
    vector<vector<int>> res;
    void dfs(vector<int> &nums, int st, vector<int> &temp) {
        if (st == nums.size()) {
            res.push_back(temp);
            return;
        }

        temp.push_back(nums[st]);
        dfs(nums, st   1, temp);
        temp.pop_back();

        dfs(nums, st   1, temp);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> temp;
        dfs(nums, 0, temp);
        return res;
    }
};

class Solution {
private:
    unordered_map<char, string> map{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"},
    };
    vector<string> res;
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty())
            return res;

        string cur;
        backtrace(digits, 0, cur);
        return res;
    }

    void backtrace(string &digits, int index, string &cur) {
        if (index >= digits.size()) {
            res.push_back(cur);
            return;
        }

        for (char c: map[digits[index]]) {
            cur.push_back(c);
            backtrace(digits, index   1, cur);
            cur.pop_back();
        }
    }
};

class Solution {
private:
    static constexpr int SEG_COUNT = 4;
    vector<string> ans;
    vector<int> segments;

public:
    void dfs(const string &s, int seg_idx, int seg_st) {
        if (seg_idx == SEG_COUNT) {
            if (seg_st == s.size()) {
                string ip_addr;
                for (int i = 0; i < SEG_COUNT;   i) {
                    ip_addr  = to_string(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ip_addr  = ".";
                    }
                }
                ans.push_back(move(ip_addr));
            }
            return;
        }

        if (seg_st == s.size())
            return;

        if (s[seg_st] == '0') {
            segments[seg_idx] = 0;
            dfs(s, seg_idx   1, seg_st   1);
        }

        int addr = 0;
        for (int seg_ed = seg_st; seg_ed < s.size();   seg_ed) {
            addr = addr * 10   (s[seg_ed] - '0');
            if (addr > 0 && addr <= 0xff) {
                segments[seg_idx] = addr;
                dfs(s, seg_idx   1, seg_ed   1);
            } else {
                break;
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        segments.resize(SEG_COUNT);
        dfs(s, 0, 0);
        return ans;
    }
};

class Solution {
private:
    vector<vector<int>> res;
private:
    void dfs(vector<int> &candidates, int target, vector<int> &cur, int st) {
        if (target == 0) {
            res.push_back(cur);
            return;
        }

        for (int i = st; i < candidates.size();   i) {
            int item = candidates[i];
            
            if (target - item < 0) {
                return;
            }

            cur.push_back(item);
            dfs(candidates, target - item, cur, i);
            cur.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> cur;
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, cur, 0);
        return res;
    }
};

class Solution {
private:
    vector<vector<int>> edges;
    /* 
     * 0: not searched
     * 1: searching
     * 2: finished
     */
    vector<int> visited;
    vector<int> result;
    // determine the ring
    bool valid = true;
    
public:
    void dfs(int u) {
        visited[u] = 1;    
        for (int v : edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid)
                    return;
            } else if (visited[v] == 1) { // reback to the searching, it's a ring
                valid = false;
                return;
            }
        }
        
        visited[u] = 2;
        result.push_back(u);
    }
    
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        
        for (auto info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        
        for (int i = 0; i < numCourses && valid;   i) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        
        if (!valid)
            return {};

        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int r = height.size() - 1;
        int l = 0;

        int best = 0;
        while (l < r) {
            int cur = min(height[l], height[r]) * (r - l);
            best = max(best, cur);

            height[l] < height[r] ? l   : r--;
        }

        return best;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto num: nums) {
            ans ^= num;
        }
        
        return ans;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32;   i) {
            int total = 0;
            for (auto num : nums)
                total  = (num >> i) & 1;
            
            if (total % 3)
                ans |= (1 << i);
        }
        
        return ans;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int num: nums) {
            b = ~a & (b ^ num);
            a = ~b & (a ^ num);
        }
        return b;
    }
};

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2, 0);
        long temp = 0;
        for (auto num: nums)
            temp ^= num;
        
        temp &= ~(temp - 1);

        for (auto num: nums) {
            if (num & temp)
                res[0] ^= num;
            else
                res[1] ^= num;
        }
            
        return res;
    }
};

int lengthOfLongestSubstring(char *s) {
    int st = -1, ed = 0, res = 0;
    char c;
    int map[128];
    memset(map, -1, sizeof(map));
    for (; (c = s[ed]);   ed) {
        if (map[c] != -1 && map[c] > st) {
            st = map[c];
        }
        map[c] = ed;
        res = ed - st > res ? ed - st : res;
    }
    return res;
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int max_len = 0;
        int st = -1;
        
        for (int i = 0; i < s.size();   i) {
            char c = s[i];
            if (map.count(c) && map[c] > st) {
                st = map[c];
            }

            map[c] = i;
            max_len = max(max_len, i - st);
        }

        return max_len;
    }
};

class Solution {
private:
    int atMostDistinct(vector<int> arr, int k) {
        int len = arr.size();
        vector<int> freq(len   1);

        int l = 0, r = 0;
        int count = 0;
        int res = 0;

        while (r < len) {
            if (freq[arr[r]] == 0)
                count  ;
            freq[arr[r]]  ;
            r  ;

            while (count > k) {
                freq[arr[l]]--;
                if (freq[arr[l]] == 0)
                    count--;
                l  ;
            }

            res  = r - l;
        }

        return res;
    }
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return atMostDistinct(nums, k) - atMostDistinct(nums, k - 1);
    }
};

class Solution {
public:
    unordered_map <char, int> ori, cnt;

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t)
            ori[c]  ;

        int len = INT_MAX, ansL = -1, ansR = -1;

        for (int l = 0, r = 0; r < s.size();   r) {
            if (ori.count(s[r])) {
                cnt[s[r]]  ;
            }

            while (check() && l <= r) {
                if ((r - l   1) < len) {
                    ansL = l;
                    len = r - l   1;
                }

                if (ori.count(s[l])) {
                    cnt[s[l]]--;
                }

                l  ;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        deque<int> q;
        for (int i = 0; i < k;   i) {
            while (!q.empty() && nums[q.back()] < nums[i])
                q.pop_back();
            q.push_back(i);
        }

        vector<int> res({nums[q.front()]});
        for (int i = k; i < nums.size();   i) {
            while (!q.empty() && nums[q.back()] < nums[i])
                q.pop_back();
            q.push_back(i);

            if (q.front() < i - k   1)
                q.pop_front();
            res.push_back(nums[q.front()]);
        }

        return res;
    }
};

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (char c : s) {
            switch (c) {
                case '(':
                case '{':
                case '[':
                    stk.push(c);
                    break;
                case ')':
                    if (stk.empty() || stk.top() != '(')
                        return false;
                    stk.pop();
                    break;
                case '}':
                    if (stk.empty() || stk.top() != '{')
                        return false;
                    stk.pop();
                    break;
                case ']':
                    if (stk.empty() || stk.top() != '[')
                        return false;
                    stk.pop();
                    break;
                default:
                    return false;
            }
        }
        
        if (stk.empty())
            return true;
        else
            return false;
    }
}

class Solution {
private:
    int m_res = 0;
public:
    int trap(vector<int>& height) {
        stack<int> stk;
        int btm_h, l_idx, h;
        for (int r_idx = 0; r_idx < height.size();   r_idx) {
            while (!stk.empty() && height[stk.top()] < height[r_idx]) {
                btm_h = height[stk.top()];
                stk.pop();
                if (stk.empty())
                    break;
                
                l_idx = stk.top();
                h = min(height[l_idx], height[r_idx]) - btm_h;
                m_res  = (r_idx - l_idx - 1) * h;           
            }
            
            stk.push(r_idx);
        }
        
        return m_res;
    }
};

class Solution {
private:
    int res = 0;
public:
    int longestValidParentheses(string s) {
        stack<int> stk({-1});
        
        for (int i = 0; i < s.length();   i) {
            if (s[i] == '(')
                stk.push(i);
            else {  // c == ')'
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    res = max(res, i - stk.top());
                }
            }
        }
        
        return res;
    }
};

class MinStack {
private:
    stack<int> stk;
    stack<int> min_stk;

public:
    MinStack() {
        stk.push(INT_MAX);
        min_stk.push(INT_MAX);
    }

    void push(int val) {
        int cur_min = min(min_stk.top(), val);
        stk.push(val);
        min_stk.push(cur_min);
    }

    void pop() {
        stk.pop();
        min_stk.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return min_stk.top();
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int first, second, third;
        vector<vector<int>> ans;

      	// 注意这里强转了 int, 如果不, num.size() 是一个 unsigned long 类型
      	// 0 - 2 会是一个非常大的数字
        for (first = 0; first < (int) nums.size() - 2;   first) {
            if (first > 0 && nums[first] == nums[first - 1])
                continue;

            second = first   1;
            third = nums.size() - 1;
            while (second < third) {
                if (second > first   1 && nums[second] == nums[second - 1]) {
                    second  ;
                    continue;
                }

                int target = -nums[first];
                int two_sum = nums[second]   nums[third];
                if (two_sum < target)
                    second  ;
                else if (two_sum > target)
                    third--;
                else {
                    ans.push_back(vector<int>{nums[first], nums[second], nums[third]});
                    second  ;
                    third--;
                }
            }
        }

        return ans;
    }
};

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int nums_len = nums.size();
        int best = e7;

        auto update = [&](int cur) {
            if (abs(cur - target) < abs(best -target))
                best = cur;
        };

        for (int i = 0; i < nums_len;   i) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            int j = i   1, k = nums_len - 1;
            while (j < k) {
                int sum = nums[i]   nums[j]   nums[k];
                
                if (sum == target)
                    return target;

                update(sum);
                if (sum > target)
                    k--;
                else
                    j  ;
            }
        }
        
        return best;
    }
};

bool isStraight(int *nums, int numsSize) {
    int set[14];
    int m_min = INT32_MAX, m_max = INT32_MIN;
    memset(set, 0, sizeof(set));
    for (int i = 0; i < numsSize;   i) {
        if (nums[i] == 0)
            continue;

        if (set[nums[i]]  )
            return false;

        m_min = m_min < nums[i] ? m_min : nums[i];
        m_max = m_max > nums[i] ? m_max : nums[i];
    }
    return m_max - m_min < 5;
}

int *construct_state_machine(char *word, size_t word_len) {
    if (word_len == 0)
        return NULL;
    int *pi = (int *) malloc(sizeof(int) * word_len);
    if (!pi)
        return NULL;

    int j = 0;
    pi[0] = 0;
    for (int i = 1; i < word_len;   i) {
        while (word[i] != word[j] && j > 0)
            j = pi[j - 1];

        if (word[i] == word[j])
            pi[i] =   j;
        else
            pi[i] = j;
    }

    return pi;
}

int strStr(char *word, char *pattern) {
    int m = strlen(word);
    int n = strlen(pattern);

    int *pi = construct_state_machine(pattern, n);
    if (!pi)
        return 0;

    for (int i = 0, j = 0; i < m;   i) {
        while (j > 0 && word[i] != pattern[j])
            j = pi[j - 1];
        if (word[i] == pattern[j])
            j  ;
        if (j == n)
            return i - n   1;
    }

    free(pi);
    return -1;
}