/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct cmp {
    bool operator () (pair<float, int>& A, pair<float, int>& B) {
        return A.first < B.first;
    }
};

class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        
        priority_queue<pair<float, int>, vector<pair<float, int>>, cmp> pq;
        inOrderTraverse(root, target, k, pq);
        vector<int> ret;
        while (!pq.empty()) {
            ret.push_back(pq.top().second);
            pq.pop();
        }
        return ret;
    }
    
    void inOrderTraverse(TreeNode* root, double target, int k, 
         priority_queue<pair<float, int>, vector<pair<float, int>>, cmp>& pq) {
        if (root == NULL) return;
        inOrderTraverse(root->left, target, k, pq);
        auto pa = make_pair(abs(root->val - target), root->val);
        if (pq.size() >= k) {
            if (pa.first < pq.top().first) {
                pq.pop();
                pq.push(pa);
            } 
        }else {
            pq.push(pa);
        }
        inOrderTraverse(root->right, target, k, pq);
    }
};

#define RANGE 300
class HitCounter {
public:
    map<int, int> times;
    int count;
    int pre;
    /** Initialize your data structure here. */
    HitCounter() {
        count = 0;
        pre = -1;
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        if (pre != timestamp){
            times[timestamp] = count; 
            pre = timestamp;
        } 
        ++count;
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        int start = timestamp - RANGE + 1;
        auto iter = times.lower_bound(start);
        if (iter == times.end() ) return 0;
        return count - iter->second;
    }
};

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */

/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * class Robot {
 *   public:
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     bool move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     void turnLeft();
 *     void turnRight();
 *
 *     // Clean the current cell.
 *     void clean();
 * };
 */
class Solution {
public:
    void cleanRoom(Robot& robot) {
        int x = 0;
        int y = 0;    
        unordered_map<int, unordered_map<int, bool>> visited;
        int direction = 0;
        cleanHelper(robot, visited, x, y, direction);
        return;
    }
    
    void cleanHelper(Robot& robot, unordered_map<int, unordered_map<int, bool>>& visited, int x, int y, int direction) {
        if (visited[x][y] == true) return;
        vector<vector<int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        visited[x][y] = true;
        robot.clean();
        for (int i = 0; i < 4; ++i) {
            if (robot.move()) {
                cleanHelper(robot, visited, x + directions[direction][0], y + directions[direction][1], direction);
                robot.turnLeft();
                robot.turnLeft();
                robot.move();
                robot.turnLeft();
                robot.turnLeft();
            }
            robot.turnLeft();
            direction = (direction + 1) % 4;
        }
        return;
    }
    
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
    
public:
    bool static compare(Interval& a, Interval& b) {
        return a.start < b.start;
    }
    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
        vector<Interval> whole;
        for (auto& item : schedule) {
            for (auto& item2 : item) {
                whole.push_back(item2);
            }
        }
        sort(whole.begin(), whole.end(), compare);
        
        int pre = -1;
        vector<Interval> merged;
        for (int index = 0; index < whole.size(); ++index) {
            if (whole[index].start > pre) {
                merged.push_back(whole[index]);
            }else {
                merged[merged.size() - 1].end = 
                    max(whole[index].end, merged[merged.size() - 1].end);
            }
            pre = merged[merged.size() - 1].end;
        }
        vector<Interval> ret;
        for (int index = 0; index < merged.size() - 1; ++index) {
            ret.push_back(Interval(merged[index].end, merged[index + 1].start));
        }
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == NULL) return ret;
        map<int, map<int, vector<int>>> matrix;
        traverseNode(root, matrix, 0, 0);
        for (auto& item1 : matrix) {
            vector<int> vec;
            cout << item1.first << endl;
            for (auto& item2 : item1.second) {
                for (auto& item3 : item2.second) {
                    vec.push_back(item3);
                }
            }
            ret.push_back(vec);
        }
        
        return ret;
    }
    
    void traverseNode(TreeNode* root, map<int, map<int, vector<int>> >& matrix, int depth, int width) {
        if (root == NULL) return;
        traverseNode(root->left, matrix, depth + 1, width - 1);
        matrix[width][depth].push_back(root->val);
        traverseNode(root->right, matrix, depth + 1, width + 1);
        return;
    }
};

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int size = nestedList.size();
        vector<pair<int, int>> slot;
        if (size == 0) return 0;
        int maxDepth = -1;
        for (int i = 0; i < size; ++i) {
            findDepth(slot, nestedList[i], 1, maxDepth);
        }
        int ret = 0;
        for (int i = 0 ;i < slot.size(); ++i) {
            ret += (maxDepth + 1 - slot[i].first) * slot[i].second;
        }
        return ret;
    }
    
    void findDepth(vector<pair<int, int>>& slot, NestedInteger& nested, int currentDepth, int& maxDepth) {
        maxDepth = max(currentDepth, maxDepth);
        if (nested.isInteger()) {
            slot.push_back(make_pair(currentDepth, nested.getInteger()) ); 
            return;
        } 
        auto& lis = nested.getList();
        for (int i = 0; i < lis.size(); ++i) {
            findDepth(slot, lis[i], currentDepth + 1, maxDepth);
        }
        return;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == NULL) return NULL;
        unordered_map<TreeNode*, int> mapping;
        vector<TreeNode*> vec;
        int index = 0;
        traverseNode(mapping, vec, root);
        int targetIndex = mapping[p];
        if (targetIndex >= vec.size() - 1) return NULL;
        return vec[targetIndex + 1];
    }
    
    void traverseNode(unordered_map<TreeNode*, int>& mapping, vector<TreeNode*>& vec, TreeNode* root) {
        if (root == NULL) return;
        traverseNode(mapping, vec, root->left);
        mapping[root] = vec.size();
        vec.push_back(root);
        traverseNode(mapping, vec, root->right);
        return;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == NULL) return NULL;
        TreeNode* traverse = root;
        TreeNode* ret = NULL;
        
        while (traverse) {
            if (p->val < traverse->val) {
                ret = traverse;
                traverse = traverse->left;
            }else {
                traverse = traverse->right;
            }
            
        }
        
        return ret;
    }
    
};

class SnakeGame {
private:
    // vector<vector<int>> grid;
    int headX;
    int headY;
    int count;
    int height;
    int width;
    queue<pair<int, int>> que;
    unordered_map<string, pair<int, int>> directions;
    map<pair<int, int>, bool> occupied;
    vector<pair<int, int>> foods;
public:
    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    SnakeGame(int width, int height, vector<pair<int, int>> food) {
        // vector<vector<int>> newGrid(height, vector<int>(width));
        // grid = newGrid;
        directions["R"] = make_pair(0, 1);
        directions["L"] = make_pair(0, -1);
        directions["U"] = make_pair(-1, 0);
        directions["D"] = make_pair(1, 0);
        this->height = height;
        this->width = width;
        headX = 0;
        headY = 0;
        
        que.push(make_pair(headX, headY));
        occupied[make_pair(headX, headY)] = true;
        count = 0;
        foods = food;
    }
    
    /** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */
    int move(string direction) {
        int newX = headX + directions[direction].first;
        int newY = headY + directions[direction].second;
        
        //Hit the wall
        if (newX < 0 || newX >= height || newY < 0 || newY >= width) return -1;
        
        
        //Pay attention to the order of push and pop, we should try pop(shorten) the snake befroe we push pos into it.
        if (count < foods.size() && newX == foods[count].first && newY == foods[count].second) count += 1;
        else {
            pair<int, int> erase = que.front();
            que.pop();
            occupied.erase(erase);
        }
        
        if (occupied.count(make_pair(newX, newY)) != 0) return -1; //Hit itself
        occupied[make_pair(newX, newY)] = true;
        que.push(make_pair(newX, newY));
        
        headX = newX;
        headY = newY;
        
        return count;
    }
};

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int size = A.size();
        unordered_map<int, int> counter;
        for (int i = 0; i < size; ++i) counter[A[i]] = i;
        
        vector<vector<int>> dp(size, vector<int>(size, 2));
        
        int ret = 0;
        for (int i = 1; i < size - 1; ++i) {
            for (int j = i + 1; j < size; ++j){
                int target = A[j] - A[i];
                if (target >= A[i]) break;
                auto iter = counter.find(target);
                if (iter == counter.end()) continue;
                dp[i][j] = dp[iter->second][i] + 1;
                ret = max(ret, dp[i][j]);
            }
        }
        return ret;
    }
};

class TicTacToe {
private:
    vector<vector<int>> grid;
    vector<int> rowSum;
    vector<int> rowProduct;
    vector<int> colSum;
    vector<int> colProduct;
    vector<int> diagonalSum;
    vector<int> diagonalProduct;
    int size;
    vector<int> playerProduct;
public:
    /** Initialize your data structure here. */
    TicTacToe(int n) {
        vector<vector<int>> newGrid(n, vector<int>(n, 0));
        grid = newGrid;
        
        //Target
        playerProduct.push_back(1);
        playerProduct.push_back(1 << n);
        
        //Sum
        rowSum.resize(n);
        colSum.resize(n);
        diagonalSum.resize(2);
        
        //Product
        for (int i = 0; i < n; ++i) {
            rowProduct.push_back(1);
            colProduct.push_back(1);
        }
        diagonalProduct.push_back(1);
        diagonalProduct.push_back(1);
        size = n;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    int move(int row, int col, int player) {
        grid[row][col] = player;
        
        
        rowSum[row] += player;
        rowProduct[row] *= player;
        
        colSum[col] += player;
        colProduct[col] *= player;
        
        if (int pos = diagonal(row, col)) {
            if (pos == 3) {
                diagonalSum[0] += player;
                diagonalSum[1] += player;
                diagonalProduct[0] *= player;
                diagonalProduct[1] *= player;
            }else {
                diagonalSum[pos - 1] += player; 
                diagonalProduct[pos - 1] *= player;
            }
            
            
            if ( (diagonalSum[0] == size * player 
                && diagonalProduct[0] == playerProduct[player - 1]) 
               || (diagonalSum[1] == size * player 
                && diagonalProduct[1] == playerProduct[player - 1])
               ) 
                return player;
        }
        
        if ( (rowSum[row] == size * player && rowProduct[row] == playerProduct[player - 1]) 
            || (colSum[col] == size * player && colProduct[col] == playerProduct[player - 1]) )
            return player;
        
        return 0;
    }
    
    int diagonal(int row, int col) {
        if (size % 2 && row == size / 2 && col == size / 2) return 3;
        if (row == col) return 2;
        if (row + col == size - 1) return 1;
        return 0;
    }
};

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */