// LRU Cache
class LRUCache {
 public:
  unordered_map<int,pair<int, list<int>::iterator>> _rec;
  int _capacity;
  list<int> _keyset;
    
  LRUCache(int capacity) {
    _capacity = capacity;
  }
    
  int get(int key) {
    if (_rec.find(key) != _rec.end()) {
      _keyset.erase(_rec[key].second);
      _keyset.push_front(key);
      _rec[key] = make_pair(_rec[key].first, _keyset.begin());
      return _rec[key].first; 
    }
    return -1;
  }
    
  void put(int key, int value) {
    if (_keyset.size() >= _capacity && _rec.find(key) == _rec.end()) {
      int rm_key = _keyset.back();
      _keyset.pop_back();
      _rec.erase(rm_key);
    }
    if (_rec.find(key) != _rec.end()) {
      _keyset.erase(_rec[key].second);
    }
    _keyset.push_front(key);
    _rec[key] = make_pair(value, _keyset.begin());
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

// LFU Cache
// unordered_map, visit times->list of data; 
// unordered_map, key->pair(count, key iterator, val)
class LFUCache {
 public:
  class VALUE{
   public:
    int _value;
    int _cnt;
    list<int>::iterator _listItr;
    VALUE(int v, int c, list<int>::iterator list_itr) {
      _value = v;
      _cnt = c;
      _listItr = list_itr;
    }
  };
    
  int _capacity;
  int _minCnt;
  unordered_map<int, VALUE*> _recKey;
  unordered_map<int, list<int>> _hirarchCache;
    
  LFUCache(int capacity) {
    _capacity = capacity;
    _minCnt = 0;
  }
    
  int get(int key) {
    if (_recKey.find(key) == _recKey.end() || _capacity <= 0) {
      return -1;
    }
        
    auto cur_node = _recKey[key];
    _hirarchCache[cur_node->_cnt].erase(cur_node->_listItr);
    if (_minCnt == cur_node->_cnt && !_hirarchCache[cur_node->_cnt].size()) {
      ++_minCnt;
    }
    cur_node->_cnt++;
    _hirarchCache[cur_node->_cnt].push_front(key);
    _recKey[key] = new VALUE(cur_node->_value, cur_node->_cnt, _hirarchCache[cur_node->_cnt].begin());
        
    return cur_node->_value;
  }
    
  void put(int key, int value) {
    if (_capacity <= 0) {
      return;
    }
    if (_recKey.find(key) == _recKey.end() && _recKey.size() < _capacity) {
      _hirarchCache[1].push_front(key);
      VALUE* new_value = new VALUE(
          value,
          1,
          _hirarchCache[1].begin()
      );
      _recKey.insert(make_pair(key, new_value));
      _minCnt = 1;
      return;
    }
        
    if (_recKey.find(key) != _recKey.end()) {
      auto cur_node = _recKey[key];
      _hirarchCache[cur_node->_cnt].erase(cur_node->_listItr);
      if (_minCnt == cur_node->_cnt && !_hirarchCache[cur_node->_cnt].size()) {
        ++_minCnt;
      }
      cur_node->_cnt++;
      _hirarchCache[cur_node->_cnt].push_front(key);
      _recKey[key] = new VALUE(
                value, 
                cur_node->_cnt,                       
                _hirarchCache[cur_node->_cnt].begin());
      return;
    }
        
    auto cur_layer = _hirarchCache[_minCnt];
    int rm_key = cur_layer.back();
        
    _hirarchCache[_minCnt].pop_back();
    _recKey.erase(rm_key);
    _minCnt = 1;
    _hirarchCache[1].push_front(key);
    _recKey[key] = new VALUE(
               value,
               1,
               _hirarchCache[1].begin());
  }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

// Min Stack
// Two stack, one is normal, the other is the min stack.
class MinStack {
 public:
  stack<int> stk1;
  stack<int> stk2;
  /** initialize your data structure here. */
  MinStack() {}
    
  void push(int x) {
    stk1.push(x);
    if(stk2.empty() || x<=getMin())
        stk2.push(x);
  }
    
  void pop() {
    if(stk1.top()==stk2.top())
        stk2.pop();
    stk1.pop();
  }
    
  int top() {
    return stk1.size()?stk1.top():INT_MAX;
  }
    
  int getMin() {
    return stk2.size()?stk2.top():INT_MAX;
  }
};

// 170. Two Sum III - Data structure design. Hash table; or tow sum with status(sorted) or not.

// 173. Binary Search Tree Iterator
// 1. Inorder go through with store in a vector, then later is easier.
// 2. With iteration version of the in-order
class BSTIterator {
 public:
  stack<TreeNode*> record;
  BSTIterator(TreeNode* root) {
    while (root != nullptr)  {
      record.push(root);
      root = root->left;
    }      
  }
    
  /** @return the next smallest number */
  int next() {
    const auto tpr = record.top();
    const int tpr_val = tpr->val;
    record.pop();
    auto tpr_right = tpr->right;
    while (tpr_right != nullptr) {
      record.push(tpr_right);
      tpr_right = tpr_right->left;
    }
    return tpr_val;
  }
    
  /** @return whether we have a next smallest number */
  bool hasNext() {
    return record.size() > 0;    
  }
};

// 225. Implement Stack using Queues
// Push: O(n); Pop: O(1). Only one queue.

// 297. Serialize and Deserialize Binary Tree
// Using level interator to go through
/**
 * 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 {
 private:
  vector<TreeNode*> ParseElement(const string& data) {
    vector<TreeNode*> nodes;
    int num = 0;
    int pos = 1;
    for (const auto& c : data) {
      if (c == ',') {
        nodes.push_back(num == INT_MIN? nullptr : new TreeNode(num*pos));
        num = 0;
        pos = 1;
      } else if (c == 'n') {
        num = INT_MIN;
      } else if (c == '-') {
        pos = -1;
        num = 0;
      } 
      else {
        num = num*10 + c - '0';
      }
    }
    return nodes;
  }
  
 public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    string serialize_str;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
      int size = que.size();
      for (int i = 0; i < size; ++i) {
        const auto node = que.front();
        que.pop();
        serialize_str += node?to_string(node->val)+",":"n,";
        if (node) {
          que.push(node->left);
          que.push(node->right);
        }
      }
    }
    cout << serialize_str << endl;
    return serialize_str;
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    vector<TreeNode*> nodes = ParseElement(data);    
    queue<TreeNode*> que;
    que.push(nodes[0]);
    int idx = 1;
    while (!que.empty()) {
      int size = que.size();
      for (int i = 0; i < size; ++i) {
        auto tp = que.front();
        que.pop();
        if (tp) {
          tp->left = nodes[idx++];
          tp->right = nodes[idx++];
          que.push(tp->left);
          que.push(tp->right);
        }
      }
    }
    return nodes[0];
  }
};

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

// 355. Design Twitter
class Twitter {
 public:
  class Compare {
   public:
    bool operator()(const pair<int, int>&p1, const pair<int, int>& p2) {
      return p1.second > p2.second;
    }
  };
  
  unordered_map<int, unordered_set<int>> follower_ids_;
  unordered_map<int, vector<pair<int, int>>> posts_;
  int count_ = 0;
  
  /** Initialize your data structure here. */
  Twitter() {}
    
  /** Compose a new tweet. */
  void postTweet(int userId, int tweetId) {
    posts_[userId].push_back({tweetId, count_++});
  }
    
  /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
  vector<int> getNewsFeed(int userId) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    int cnt = 0;
    for (auto it = posts_[userId].crbegin(); it != posts_[userId].crend(); ++it) {
      if (pq.size() < 10) {
        pq.push(*it);
      } else {
        if (it->second < pq.top().second) break;
        pq.push(*it);
      }
    }
    
    for (auto id = follower_ids_[userId].begin(); id != follower_ids_[userId].end(); ++id) {
      for (auto it = posts_[*id].crbegin(); it != posts_[*id].crend(); ++it) {
        if (pq.size() < 10) {
          pq.push(*it);
        } else {
          if (it->second < pq.top().second) break;
          pq.pop();
          pq.push(*it);
        }
      }
    }
    vector<int> ans;
    while (!pq.empty()) {
      ans.push_back(pq.top().first);
      pq.pop();
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
    
  /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
  void follow(int followerId, int followeeId) {
    if (followerId != followeeId) {
      follower_ids_[followerId].insert(followeeId);
    }
  }
    
  /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
  void unfollow(int followerId, int followeeId) {
    follower_ids_[followerId].erase(followeeId);    
  }
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */

// 379. Design Phone Directory
class PhoneDirectory {
 public:
  vector<bool> record_;
  int pos_ = -1;
  
  /** Initialize your data structure here
      @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
  PhoneDirectory(int maxNumbers) {
    record_ = vector<bool>(maxNumbers, true);
    pos_ = 0;
  }
    
  /** Provide a number which is not assigned to anyone.
      @return - Return an available number. Return -1 if none is available. */
  int get() {
    for (int i = 0; i < record_.size(); ++i) {
      const int new_pos = (pos_ + i + record_.size()) % record_.size();
      if (record_[new_pos]) {
        pos_ = (new_pos + record_.size()) % record_.size();
        record_[new_pos] = false;
        return new_pos;
      }
    }        
    return -1;
  }
    
  /** Check if a number is available or not. */
  bool check(int num) {
    return record_[(num+record_.size())%record_.size()];
  }
    
  /** Recycle or release a number. */
  void release(int num) {
    record_[(num+record_.size())%record_.size()] = true;
    pos_ = (num+record_.size())%record_.size();
  }
};

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory* obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj->get();
 * bool param_2 = obj->check(number);
 * obj->release(number);
 */

// 380. Insert Delete GetRandom O(1)
class RandomizedSet {
 private:
  unordered_map<int, int> record_;
  vector<int> data_;
  
 public:
  /** Initialize your data structure here. */
  RandomizedSet() {}
    
  /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
  bool insert(int val) {
    if (record_.find(val) != record_.end()) return false;
    record_[val] = data_.size();
    data_.push_back(val);
    return true;
  }
    
  /** Removes a value from the set. Returns true if the set contained the specified element. */
  bool remove(int val) {
    if (record_.find(val) == record_.end()) return false;
    const int idx = record_[val];
    record_.erase(val);
    const int data = data_.back();
    if (val != data) {
      record_[data] = idx;
      data_[idx] = data;  
    }
    data_.pop_back();
    return true;
  }
    
  /** Get a random element from the set. */
  int getRandom() {
    return data_[floor(1.0*rand()/RAND_MAX*record_.size())];      
  }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

// 381. Insert Delete GetRandom O(1) - Duplicates allowed
class RandomizedCollection {
 private:
  vector<int> record_;
  unordered_map<int, unordered_set<int>> position_;
 public:
  /** Initialize your data structure here. */
  RandomizedCollection() {}
    
  /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
  bool insert(int val) {
    auto& item = position_[val];
    const auto [it, s] = item.insert(record_.size());
    record_.emplace_back(val);
    return s;
  }
    
  /** Removes a value from the collection. Returns true if the collection contained the specified element. */
  bool remove(int val) {
    if (position_.find(val) == position_.end())
      return false;
    auto& item = position_[val];
    const int idx = *(position_[val].begin());
    item.erase(item.begin());
    const int val_back = record_.back();
    if (idx != record_.size()-1) {
      record_[idx] = val_back;
      position_[val_back].insert(idx);
      position_[val_back].erase(record_.size()-1);
    }
    record_.pop_back();
    if (!position_[val].size())
      position_.erase(val);
    return true;
  }
    
  /** Get a random element from the collection. */
  int getRandom() {
    return record_[floor(1.0*rand()/RAND_MAX*record_.size())];    
  }
};

// 716. Max Stack
// Two stacks are for the O(1) push and O(N) for popMax.
// O(log N) popMax.
class MaxStack {
 public:
  list<int> data_;
  map<int, stack<list<int>::iterator>> record_;
  /** initialize your data structure here. */
  MaxStack() {}
    
  void push(int x) {
    data_.push_back(x);
    record_[x].push(--data_.end());
  }
    
  int pop() {
    const int ans = data_.back();
    record_[ans].pop();
    if (!record_[ans].size()) record_.erase(ans);
    data_.pop_back();
    return ans;
  }
    
  int top() {
    return data_.back();    
  }
    
  int peekMax() {
    const int ans = *(((--record_.end())->second.top()));   
    return ans;
  }
    
  int popMax() {
    auto it = --record_.end();
    const auto it2 = (it->second.top());
    const int num = *it2;
    it->second.pop();
    data_.erase(it2);
    if (!record_[num].size())
      record_.erase(num);
    return num;
  }
};

// 588. Design In-Memory File System
class FileSystem {
 private:
  class TreeNode {
   public:
    string content_;
    unordered_map<string, TreeNode*> child;
  };
  
  vector<string> ParsePath(const string& path) {
    vector<string> ans({"/"});
    string cur;
    for (const auto& c:path) {
      if (c == '/') {  
        if (cur.size()) {
          ans.push_back(cur);
          cur.clear();
        }
      } else {
        cur += c;
      }
    }
    if (cur.size()) ans.push_back(cur);
    return ans;
  }
  
  unique_ptr<TreeNode> parent_;
  
 public:
  FileSystem() {
    parent_ = make_unique<TreeNode>();
  }
    
  vector<string> ls(string path) {
    vector<string> segments = ParsePath(path);
    TreeNode* root = parent_.get();
    for (const auto& segment : segments) {
      if (segment == "/") continue;
      if (root->child.find(segment) != root->child.end())
        root = root->child[segment];
      else
        return {};
    }
    vector<string> ans;
    if (root->content_.size()) {
      return segments.size() <= 1?vector<string>():vector<string>({segments.back()});
    } else {
      for (const auto& c : root->child) {
        // cout << "path ls -> " << c.first << endl;
        ans.push_back(c.first);
      }
      sort(begin(ans), end(ans));
      // cout << "ls " << path << "\n";
      return ans;
    }
  }
    
  void mkdir(string path) {
    vector<string> segments = ParsePath(path);    
    TreeNode* root = parent_.get();
    for (const auto& seg : segments) {
      if (seg == "/") continue;
      if (!root->child[seg])
        root->child[seg] = new TreeNode();
      root = root->child[seg];
      // cout << "mkdir " << seg << endl;
    }
  }
    
  void addContentToFile(string filePath, string content) {
    vector<string> segments = ParsePath(filePath);
    TreeNode* root = parent_.get();
    for (const auto& seg : segments) {
      if (seg == "/") continue;
      if (!root->child[seg]) {
        root->child[seg] = new TreeNode();
      }
      root = root->child[seg];
    }
    root->content_ += content;
  }
    
  string readContentFromFile(string filePath) {
    vector<string> segments = ParsePath(filePath);
    TreeNode* root = parent_.get();
    for (const auto& seg : segments) {
      if (seg == "/") continue;
      root = root->child[seg];
      if (!root) return "";
    }
    return root?root->content_:"";
  }
};

// 432. All O`one Data Structure
class AllOne {
 public:
  map<int, unordered_set<string>> record_;
  unordered_map<string, int> data_;
    
  /** Initialize your data structure here. */
  AllOne() {}
    
  /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
  void inc(string key) {
    if (data_.find(key) != data_.end()) {
      record_[data_[key]].erase(key);
      if (!record_[data_[key]].size())
        record_.erase(data_[key]);
    }
    ++data_[key];
    record_[data_[key]].insert(key);
  }
    
  /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
  void dec(string key) {
    if (data_.find(key) == data_.end())
      return;
    const int cnt = data_[key];
    --data_[key];
    if (!data_[key]) {
      data_.erase(key);
    }
    record_[cnt].erase(key);
    if (!record_[cnt].size()) {
      record_.erase(cnt);
    }
    if (data_.find(key) != data_.end())
      record_[cnt-1].insert(key);
  }
    
  /** Returns one of the keys with maximal value. */
  string getMaxKey() {
    if (!record_.size()) return "";
    return *(record_.crbegin()->second.begin());    
  }
    
  /** Returns one of the keys with Minimal value. */
  string getMinKey() {
    if (!record_.size()) return "";
    return *(record_.cbegin()->second.begin());        
  }
};
// Bucket with list & remember the list is double linked list
class AllOne {
 public:
  void inc(string key) {
    // If the key doesn't exist, insert it with value 0.
    if (!bucketOfKey.count(key))
      bucketOfKey[key] = buckets.insert(buckets.begin(), {0, {key}});
            
    // Insert the key in next bucket and update the lookup.
    auto next = bucketOfKey[key], bucket = next++;
    if (next == buckets.end() || next->value > bucket->value + 1)
      next = buckets.insert(next, {bucket->value + 1, {}});
    next->keys.insert(key);
    bucketOfKey[key] = next;
        
    // Remove the key from its old bucket.
    bucket->keys.erase(key);
    if (bucket->keys.empty())
      buckets.erase(bucket);
  }

  void dec(string key) {
    // If the key doesn't exist, just leave.
    if (!bucketOfKey.count(key))
      return;

    // Maybe insert the key in previous bucket and update the lookup.
    auto prev = bucketOfKey[key], bucket = prev--;
    bucketOfKey.erase(key);
    if (bucket->value > 1) {
      if (bucket == buckets.begin() || prev->value < bucket->value - 1)
        prev = buckets.insert(bucket, {bucket->value - 1, {}});
      prev->keys.insert(key);
      bucketOfKey[key] = prev;
    }
        
    // Remove the key from its old bucket.
    bucket->keys.erase(key);
    if (bucket->keys.empty())
      buckets.erase(bucket);
  }

  string getMaxKey() {
    return buckets.empty() ? "" : *(buckets.rbegin()->keys.begin());
  }
    
  string getMinKey() {
    return buckets.empty() ? "" : *(buckets.begin()->keys.begin());
  }

 private:
  struct Bucket { int value; unordered_set<string> keys; };
  list<Bucket> buckets;
  unordered_map<string, list<Bucket>::iterator> bucketOfKey;
};

// Design with some specific data structurt
// 705. Hash 
// Method 1: linked list hash, separate chaining. BST as a bucket.
class MyHashSet {
 private:
  vector<list<int>> hash_;
  
 public:
  /** Initialize your data structure here. */
  MyHashSet() {
    hash_.resize(769);
  }
    
  void add(int key) {
    for (auto& c : hash_[key%769]) {
      if (c == key) return;
    }    
    hash_[key%769].push_back(key);
  }
    
  void remove(int key) {
    for (auto it = begin(hash_[key%769]); it != end(hash_[key%769]); ++it) {
      if (*it == key) {
        hash_[key%769].erase(it);
        return;
      }
    }      
  }
    
  /** Returns true if this set contains the specified element */
  bool contains(int key) {
    for (auto& c : hash_[key%769]) {
      if (c == key) return true;
    }       
    return false;
  }
};
// Method 2: open addressing.
// Method 3: 2-choice hashing.

// 707. Design Linked List
class MyLinkedList {
 private:
  struct Node {
    Node* next_ = nullptr;
    int val_ = 0;
    Node(const int val) {
      next_ = nullptr;
      val_ = val;
    }
    Node(const int val, Node* next) {
      next_ = next;
      val_ = val;
    }
  };
  
  Node* head_;
  Node* tail_;
  
 public:
  /** Initialize your data structure here. */
  MyLinkedList() {
    head_ = new Node(-1);
    tail_ = head_;
  }
    
  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  int get(int index) {
    Node* cur = head_->next_;
    while (cur) {
      if (!index) break;
      --index;
      cur = cur->next_;
    }
    cout << head_->next_->val_ << " " << tail_->val_ << endl;
    return !cur ? -1:cur->val_;
  }
    
  /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  void addAtHead(int val) {
    Node* cur = new Node(val);
    Node* tmp = head_->next_;
    head_->next_ = cur;
    cur->next_ = tmp;
    if (!tmp) {
      tail_ = cur;
    }
  }
    
  /** Append a node of value val to the last element of the linked list. */
  void addAtTail(int val) {
    Node* cur = new Node(val);
    tail_->next_ = cur;
    tail_ = tail_->next_;
  }
    
  /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  void addAtIndex(int index, int val) {
    Node* cur = head_;
    while (cur) {
      if (!index) break;
      --index;
      cur = cur->next_;
    }
    if (!cur) return;
    Node* new_node = new Node(val);
    const auto tmp = cur->next_;
    cur->next_ = new_node;
    new_node->next_ = tmp;
    if (!tmp) {
      tail_ = new_node;
    }
  }
    
  /** Delete the index-th node in the linked list, if the index is valid. */
  void deleteAtIndex(int index) {
    Node* cur = head_;
    while (cur) {
      if (!index) break;
      --index;
      cur = cur->next_;
    }
    if (!cur || !cur->next_) return;    
    if (cur->next_ == tail_) 
      tail_ = cur;
    cur->next_ = cur->next_->next_;
  }
};

// 1166. Design File System
class FileSystem {
 private:
  struct Node {
    int val = -1;
    unordered_map<string, Node*> record;
  };
  
  vector<string> ParsePath(const string& path) {
    vector<string> ans;
    string cur_str;
    for (const auto& c : path) {
      if (c == '/') {
        if (!cur_str.empty())
          ans.emplace_back(cur_str);
        cur_str.clear();
      } else {
        cur_str += c; 
      }
    }
    if (!cur_str.empty())
      ans.emplace_back(cur_str);
    return ans;
  }
  
  unique_ptr<Node> parent_;
 public:
  FileSystem() {
    parent_ = make_unique<Node>();      
  }
    
  bool createPath(string path, int value) {
    if (path.empty() || path == "/")
      return false;
    Node* root = parent_.get();
    const auto paths = ParsePath(path);
    int len = 0;
    for (const auto & p : paths) {
      const auto it = root->record.find(p);
      if (it == root->record.end()) {
        if (len + 1 == paths.size())
          root->record[p] = new Node();
        else return false;
      } else {
        ++len;
      }
      root = root->record[p];
    }
    if (len == paths.size())
      return false;
    root->val = value;
    root->record.clear();
    return true;
  }
    
  int get(string path) {
    if (path.empty() || path == "/")
      return false;
    Node* root = parent_.get();
    const auto paths = ParsePath(path);
    for (const auto& p : paths) {
      const auto it = root->record.find(p);
      if (it == root->record.end())
        return -1;
      else 
        root = root->record[p];
    }
    return root->val;
  }
};

// 1286. Iterator for Combination
// Bit manipulation
class CombinationIterator {
 private: 
  bool record_[16] = {false};
  string data_;
  int len_ = 0;
  bool start_ = false;
  
 public:
  CombinationIterator(string characters, int combinationLength) {
    data_ = characters; 
    for (int i = 0; i < combinationLength; ++i) {
      record_[i] = true;
    }
    len_ = combinationLength;
  }
    
  string next() {
    string ans;
    if (start_) {
      int index_0 = -1;
      int index_1 = -1;
      int count = 0;
      for (int i = data_.size() - 1; i >= 0; --i) {
        if (!record_[i] && index_0 < 0) {
          index_0 = i;
        }
        if (record_[i] && index_0 >= 0) {
          index_1 = i;
          break;
        }
        if (record_[i]) ++count;
      }
      if (index_1 + 1 < data_.size()) {
        swap(record_[index_1], record_[index_1+1]);
      }
      for (int j = index_1+2; j < data_.size(); ++j) {
        if (count > 0) {
          record_[j] = true;
          --count;
        } else {
          record_[j] = false;
        }
      }
    }
    for (int i = 0; i < data_.size(); ++i) {
      if (record_[i]) ans += data_[i];
    }
    start_ = true;
    return ans;
  }
    
  bool hasNext() {
    int i = data_.size() - 1;
    for (i = data_.size() - 1; i >= 0; --i) 
      if (!record_[i]) break;
    return i < 0 || data_.size() - i != len_ + 1;
  }
};

// 1172. Dinner Plate Stacks
class DinnerPlates {
 private:
  int count_ = 0;
  map<int, stack<int>> record_;
  set<int> empty_stack_;
  int capacity_ = 0;
  
 public:
  DinnerPlates(int capacity) {
    capacity_ = capacity;      
  }
    
  void push(int val) {
    if (empty_stack_.empty()) {
      record_[count_].push(val);
      if (record_[count_].size() == capacity_) {
        ++count_; 
      } else {
        empty_stack_.insert(count_);
      }
    } else {
      const int index = *(empty_stack_.begin());
      record_[index].push(val);
      if (record_[index].size() == capacity_) {
        empty_stack_.erase(index);
        if (empty_stack_.empty()) ++count_;
      }
    }      
  }
    
  int pop() {
    if (record_.empty()) return -1;
    const int right = record_.rbegin()->first;
    const int tp = record_[right].top();
    record_[right].pop();
    if (record_[right].empty())
      record_.erase(right);
    empty_stack_.insert(right);
    return tp;
  }
    
  int popAtStack(int index) {
    if (record_.find(index) == record_.end()) return -1;
    const int tp = record_[index].top();
    record_[index].pop();
    empty_stack_.insert(index);
    if (record_[index].empty())
      record_.erase(index);
    return tp;
  }
};

// To do 1348.