// (newCap = oldCap << 1) < MAXIMUM_CAPACITY
int index = (capacity - 1) & root.hash;

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

public class Transaction {
  private String who;
  private Date when;
  private double amount;

  public int hashCode() {
    int hash = 1;
    hash = 31 * hash + who.hashCode();
    hash = 31 * hash + when.hashCode();
    hash = 31 * hash + ((Double) double).hashCode();
    return hash;
  }

}

public class HashTable<K, V> {
	// Some VMs reserve some header words in an array
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	// The hash table data
	private transient Entry<?, ?>[] table;
	// The total number of entries in the hash table
	private transient int count;
	// The table is rehashed when it's size exceeds this threshold (capacity * loadFactor)
	private int threshold;
	// The load factor for the hash table
	private float loadFactor;

	public HashTable() {
		int capacity = 10;
		table = new Entry<?, ?>[1];
		loadFactor = 0.75f;
		threshold = (int) Math.min(capacity * loadFactor, MAX_ARRAY_SIZE + 1);
	}

	public int size() {
		return count;
	}

	public boolean containsValue(Object value) {
		Entry<?, ?> tab[] = table;
		for (int i = tab.length; i-- > 0;) {
			for (Entry<?, ?> e = tab[i]; e != null; e = e.next) {
				if (e.value.equals(value)) {
					return true;
				}
			}
		}
		return false;
	}

	// Compare both hash and key due to different key could have same hash code
	public boolean containsKey(Object key) {
		Entry<?, ?> tab[] = table;
		int hash = key.hashCode();
		// masks off the sign bit first and then compute the remainder
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				return true;
			}
		}
		return false;
	}

	@SuppressWarnings("unchecked")
	public V get(Object key) {
		Entry<?, ?> tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				return (V) e.value;
			}
		}
		return null;
	}

	public V put(K key, V value) {
		if (value == null)
			throw new NullPointerException();

		Entry<?, ?> tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		@SuppressWarnings("unchecked")
		Entry<K, V> entry = (Entry<K, V>) tab[index];
		for (; entry != null; entry = entry.next) {
			if ((entry.hash == hash) && entry.key.equals(key)) {
				V old = entry.value;
				entry.value = value;
				return old;
			}
		}

		addEntry(hash, key, value, index);
		return null;
	}

	private void addEntry(int hash, K key, V value, int index) {
		Entry<?, ?> tab[] = table;
		if (count >= threshold) {
			rehash();
			tab = table;
			hash = key.hashCode();
			index = (hash & 0x7FFFFFFF) % tab.length;
		}
		@SuppressWarnings("unchecked")
		Entry<K, V> e = (Entry<K, V>) tab[index];
		tab[index] = new Entry<>(hash, key, value, e);
		count++;
	}

	@SuppressWarnings("unchecked")
	private void rehash() {
		int oldCapacity = table.length;
		Entry<?, ?>[] oldMap = table;

		// overflow-conscious code
		int newCapacity = (oldCapacity << 1) + 1;
		if (newCapacity - MAX_ARRAY_SIZE > 0) {
			if (oldCapacity == MAX_ARRAY_SIZE)
				// Keep running with max buckets
				return;
			newCapacity = MAX_ARRAY_SIZE;
		}
		Entry<?, ?>[] newMap = new Entry<?, ?>[newCapacity];

		threshold = (int) Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE);
		table = newMap;

		for (int i = oldCapacity; i-- > 0;) {
			for (Entry<K, V> old = (Entry<K, V>) oldMap[i]; old != null;) {
				Entry<K, V> e = old;
				old = old.next;

				int index = (e.hash & 0x7FFFFFFF) % newCapacity;
				e.next = (Entry<K, V>) newMap[index];
				newMap[index] = e;
			}
		}
	}

	private static class Entry<K, V> implements Map.Entry<K, V> {
		final int hash;
		final K key;
		V value;
		Entry<K, V> next;

		protected Entry(int hash, K key, V value, Entry<K, V> next) {
			this.hash = hash;
			this.key = key;
			this.value = value;
			this.next = next;
		}

		public K getKey() {
			return key;
		}

		public V getValue() {
			return value;
		}

		public V setValue(V value) {
			if (value == null)
				throw new NullPointerException();
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}

		public boolean equals(Object o) {
			if (!(o instanceof Map.Entry))
				return false;
			Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
			return (key == null ? e.getKey() == null : key.equals(e.getKey()))
					&& (value == null ? e.getValue() == null : value.equals(e.getValue()));
		}

		public int hashCode() {
			return hash ^ Objects.hashCode(value);
		}

		public String toString() {
			return key.toString() + "=" + value.toString();
		}

		@SuppressWarnings("unchecked")
		protected Object clone() {
			return new Entry<>(hash, key, value, (next == null ? null : (Entry<K, V>) next.clone()));
		}
	}
}

public List<List<String>> groupAnagrams(String[] strs) {
  int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 };

  List<List<String>> result = new ArrayList<>();
  if (strs == null || strs.length == 0)
    return result;

  Map<Integer, List<String>> map = new HashMap<>();
  for (String s : strs) {
    int key = 1;
    for (char c : s.toCharArray()) {
      key *= prime[c - 'a'];
    }
    if (!map.containsKey(key))
      map.put(key, new ArrayList<>());
    map.get(key).add(s);
  }
  result.addAll(map.values());
  return result;
}

// Count the characters!
public List<List<String>> groupAnagrams2(String[] strs) {
    if (strs.length == 0 || strs.length == 0)
        return new ArrayList<>();
    Map<String, List<String>> ans = new HashMap<>();
    int[] count = new int[26];
    for (String s : strs) {
        Arrays.fill(count, 0);
        for (char c : s.toCharArray())
            count[c - 'a']++;
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < 26; i++) {
            sb.append('#');
            sb.append(count[i]);
        }
        String key = sb.toString();
        // String key = Arrays.toString(count);
        if (!ans.containsKey(key))
            ans.put(key, new ArrayList<>());
        ans.get(key).add(s);
    }
    return new ArrayList<>(ans.values());
}

public int longestDistinctSubset(String s) {
    if (s.length() == 0)
        return 0;
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    // l = left, r = right
    int max = 0, l = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (map.containsKey(c)) {
            // need to track max, otherwise "abba" will fail
            l = Math.max(l, map.get(c) + 1);
        }
        map.put(c, r);
        max = Math.max(max, r - l + 1);
    }
    return max;
}

public int lengthOfLongestSubstringKDistinct(String str, int distinct) {
  if (str == null || str.length() == 0 || distinct <= 0)
    return 0;
  Map<Character, Integer> counter = new HashMap<>();
  int maxLen = 0, lo = 0;
  for (int hi = 0; hi < str.length(); hi++) {
    counter.compute(str.charAt(hi), (k, v) -> v == null ? 1 : v + 1);
    while (counter.size() > distinct) {
      counter.compute(str.charAt(lo), (k, v) -> v - 1);
      counter.remove(str.charAt(lo), 0);
      lo++;
    }
    maxLen = Math.max(maxLen, hi - lo + 1);
  }
  return maxLen;
}

public int totalFruit(int[] tree) {
  Map<Integer, Integer> counter = new HashMap<>();
  int ans = 0, l = 0;
  for (int r = 0; r < tree.length; r++) {
    counter.compute(tree[r], (k, v) -> v == null ? 1 : v + 1);
    while (counter.size() > 2) {
      counter.compute(tree[l], (k, v) -> v - 1);
      if (counter.get(tree[l]) == 0)
        counter.remove(tree[l]);
      l++;
    }
    ans = Math.max(ans, r - l + 1);
  }
  return ans;
}

public int longestSubstring(String s, int k) {
  return helper(s.toCharArray(), 0, s.length(), k);
}

public int helper(char[] s, int left, int right, int k) {
  if (right - left < k)
    return 0;
  int[] count = new int[26];
  for (int i = left; i < right; i++)
    count[s[i] - 'a']++;
  for (int i = left; i < right; i++) {
    // find the range (i, j) which has repeated characters < k
    // then exclude them with next level search!
    if (count[s[i] - 'a'] < k) {
      int j = i + 1;
      while (j < right && count[s[j] - 'a'] < k)
        j++;
      return Math.max(helper(s, left, i, k), helper(s, j, right, k));
    }
  }
  return right - left;
}

public int longestConsecutive(int[] nums) {
  Set<Integer> set = new HashSet<>();
  for (int num : nums) {
    set.add(num);
  }

  int maxLength = 0;

  for (int num : set) {
    if (!set.contains(num - 1)) {
      int currentNum = num;
      int currentLength = 1;

      while (set.contains(currentNum + 1)) {
        currentNum += 1;
        currentLength += 1;
      }

      maxLength = Math.max(maxLength, currentLength);
    }
  }

  return maxLength;
}

  public int longestConsecutive2(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int maxLength = 0;
    
    for (int num : nums) {
      if (!map.containsKey(num)) {
        int left = map.getOrDefault(num - 1, 0);
        int right = map.getOrDefault(num + 1, 0);
        int total = left + right + 1;

        maxLength = Math.max(maxLength, total);
        map.put(num, total);

        // Only need to update head and tail
        map.put(num - left, total);
        map.put(num + right, total);
      }
    }

    return maxLength;
  }

public String minWindowSubset(String s, String t) {
  if (s == null || s.length() == 0 || t == null || t.length() == 0 || s.length() < t.length())
    return "";

  int counter = t.length(), start = -1, end = s.length();
  Deque<Integer> queue = new LinkedList<>();
  Map<Character, Integer> map = new HashMap<>();

  // count target's characters
  for (char c : t.toCharArray()) {
    map.put(c, map.getOrDefault(c, 0) + 1);
  }

  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (!map.containsKey(c))
      continue;

    // track position and count down
    int n = map.get(c);
    queue.add(i);
    map.put(c, n - 1);
    if (n > 0)
      counter--;

    // keep all counts <= 0, means T is all covered
    // remove the old/duplicate char index if any
    char head = s.charAt(queue.peek());
    while (map.get(head) < 0) {
      queue.poll();
      map.put(head, map.get(head) + 1);
      head = s.charAt(queue.peek());
    }

    if (counter == 0) {
      int newLen = queue.peekLast() - queue.peek() + 1;
      if (newLen < end - start) {
        start = queue.peek();
        end = queue.peekLast() + 1;
      }
    }

  }

  if (counter == 0)
    return s.substring(start, end);
  else
    return "";
}

public String minWindow(String s, String t) {
  int[] map = new int[128];
  for (char c : t.toCharArray())
    map[c]++;
  int counter = t.length(), begin = 0, end = 0, distance = Integer.MAX_VALUE, head = 0;
  while (end < s.length()) {
    if (map[s.charAt(end++)]-- > 0)
      counter--;
    while (counter == 0) { // valid
      if (end - begin < distance)
        distance = end - (head = begin);
      if (map[s.charAt(begin++)]++ == 0)
        counter++; // make it invalid
    }
  }
  return distance == Integer.MAX_VALUE ? "" : s.substring(head, head + distance);
}

// Iterative searching to narrow down range
public String minWindowSubsequence(String S, String T) {
  String output = "";
  int minLen = 20001;
  for (int i = 0; i <= S.length() - T.length(); i++) {
    while (i < S.length() && S.charAt(i) != T.charAt(0)) {
      i++;
    }
    int l = find(S.substring(i, Math.min(i + minLen, S.length())), T);
    if (l != -1 && l < minLen) {
      minLen = l;
      output = S.substring(i, i + l);
    }
  }
  return output;
}

private int find(String S, String T) {
  for (int i = 0, j = 0; i < S.length() && j < T.length();) {
    if (S.charAt(i) == T.charAt(j)) {
      i++;
      j++;
      if (j == T.length()) {
        return i;
      }
    } else {
      i++;
    }
  }
  return -1;
}

// Dynamic programming to track indices
public String minWindowSubsequence2(String S, String T) {
  int m = S.length(), n = T.length();
  int[] dp = new int[m];
  Arrays.fill(dp, -1);
  for (int i = 0; i < m; i++) {
    if (S.charAt(i) == T.charAt(0))
      dp[i] = i;
  }
  for (int j = 1; j < n; j++) {
    int k = -1;
    int[] tmp = new int[m];
    Arrays.fill(tmp, -1);
    for (int i = 0; i < m; i++) {
      if (k != -1 && S.charAt(i) == T.charAt(j))
        tmp[i] = k;
      if (dp[i] != -1)
        k = dp[i];
    }
    dp = tmp; // swap it!
  }
  int start = -1, length = Integer.MAX_VALUE;
  // check the last row
  for (int i = 0; i < m; i++) {
    if (dp[i] != -1 && i - dp[i] + 1 < length) {
      start = dp[i];
      length = i - dp[i] + 1;
    }
  }
  return start == -1 ? "" : S.substring(start, start + length);
}

public class LRUCache {
  private Map<Integer, Node> cacheMap;
  private Node dummyHead, dummyTail;
  private int capacity;

  public LRUCache(int capacity) {
    if (capacity <= 0)
      throw new IllegalArgumentException();
    this.capacity = capacity;
    cacheMap = new HashMap<>();
    dummyHead = new Node(0, 0);
    dummyTail = new Node(0, 0);
    dummyHead.next = dummyTail;
    dummyTail.prev = dummyHead;
  }

  public int get(int key) {
    if (cacheMap.containsKey(key)) {
      Node node = cacheMap.get(key);
      deleteNode(node);
      addToHead(node);
      return node.value;
    }
    return -1;
  }

  public void put(int key, int value) {
    if (cacheMap.containsKey(key)) {
      Node node = cacheMap.get(key);
      node.value = value;
      deleteNode(node);
      addToHead(node);
    } else {
      Node node = new Node(key, value);
      cacheMap.put(key, node);
      if (cacheMap.size() > capacity) {
        cacheMap.remove(dummyTail.prev.key);
        deleteNode(dummyTail.prev);
      }
      addToHead(node);
    }
  }

  private void deleteNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  private void addToHead(Node node) {
    node.next = dummyHead.next;
    node.next.prev = node;
    node.prev = dummyHead;
    dummyHead.next = node;
  }

  class Node {
    int key, value;
    Node prev, next;

    public Node(int key, int value) {
      this.key = key;
      this.value = value;
    }
  }

public class LRUCache<K, V> {
  private Map<K, V> map;
  private int maxCapacity; // cache capacity

  public LRUCache(int maxCapacity) {
    // Keys are sorted on the basis of access order e.g Invoking the put, putIfAbsent, get,
    // getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge methods results in an access
    // to the corresponding entry.
    map = new LinkedHashMap<K, V>(maxCapacity, 0.75f, true) {
      private static final long serialVersionUID = 1L;
      // triggered by put and putAll
      protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
      }
    };
  }

  public V get(K key) {
    return map.getOrDefault(key, null);
  }

  public void set(K key, V value) {
    map.put(key, value);
  }
}

public class LFUCache {
  private int capacity = 0;
  private Node head = null;
  private HashMap<Integer, Integer> valueHash = new HashMap<Integer, Integer>();
  private HashMap<Integer, Node> nodeHash = new HashMap<Integer, Node>();

  public LFUCache(int capacity) {
    this.capacity = capacity;
  }

  public int get(int key) {
    if (valueHash.containsKey(key)) {
      increaseCount(key);
      return valueHash.get(key);
    }
    return -1;
  }

  public void put(int key, int value) {
    if (capacity == 0)
      return;
    if (valueHash.containsKey(key)) {
      valueHash.put(key, value);
    } else {
      if (valueHash.size() >= capacity)
        removeLeastUsed();
      valueHash.put(key, value);
      addToHead(key);
    }
    increaseCount(key);
  }

  private void addToHead(int key) {
    if (head == null) {
      head = new Node(0);
      head.keys.add(key);
    } else if (head.count > 0) {
      Node node = new Node(0);
      node.keys.add(key);
      node.next = head;
      head.prev = node;
      head = node;
    } else {
      head.keys.add(key);
    }
    nodeHash.put(key, head);
  }

  private void increaseCount(int key) {
    Node node = nodeHash.get(key);
    node.keys.remove(key);

    if (node.next == null) {
      node.next = new Node(node.count + 1);
      node.next.prev = node;
      node.next.keys.add(key);
    } else if (node.next.count == node.count + 1) {
      node.next.keys.add(key);
    } else {
      Node tmp = new Node(node.count + 1);
      tmp.keys.add(key);
      tmp.prev = node;
      tmp.next = node.next;
      node.next.prev = tmp;
      node.next = tmp;
    }

    nodeHash.put(key, node.next);
    if (node.keys.size() == 0)
      removeNode(node);
  }

  private void removeLeastUsed() {
    if (head == null)
      return;
    int leastUsed = head.keys.iterator().next();
    head.keys.remove(leastUsed);
    if (head.keys.size() == 0)
      removeNode(head);
    nodeHash.remove(leastUsed);
    valueHash.remove(leastUsed);
  }

  private void removeNode(Node node) {
    if (node.prev == null) {
      head = node.next;
    } else {
      node.prev.next = node.next;
    }
    if (node.next != null) {
      node.next.prev = node.prev;
    }
  }

  private class Node {
    private int count = 0;
    private Set<Integer> keys = new LinkedHashSet<Integer>();
    private Node prev = null, next = null;

    private Node(int count) {
      this.count = count;
    }
  }
}