#include <iostream>
#include <limits>

using namespace std;

// 快速乘
// x 和 y 是负数，z 是正数
// 判断 z * y >= x 是否成立
bool quickAdd(int y, int z, int x) {
  int result = 0, add = y;
  while (z > 0) { // 不能使用除法
    if (z & 1) {
      // 需要保证 result + add >= x
      if (result < x - add) {
        return false;
      }
      result += add;
    }
    if (z != 1) {
      // 需要保证 add + add >= x
      if (add < x - add) {
        return false;
      }
      add += add;
    }
    z >>= 1;
  }
  return true;
}

int divide(int a, int b) {
  if (a == numeric_limits<int>::min()) { // 考虑被除数为最小值的情况
    if (b == 1) {
      return numeric_limits<int>::min();
    }
    if (b == -1) {
      return numeric_limits<int>::max();
    }
  }
  if (b == numeric_limits<int>::min()) { // 考虑除数为最小值的情况
    if (a == numeric_limits<int>::min()) {
      return 1;
    }
    return 0;
  }
  if (a == 0) { // 考虑被除数为 0 的情况
    return 0;
  }

  // 一般情况，使用二分查找
  // 将所有的正数取相反数，这样就只需要考虑一种情况
  bool rev = false;
  if (a > 0) {
    a = -a;
    rev = !rev;
  }
  if (b > 0) {
    b = -b;
    rev = !rev;
  }

  int ans = 0;
  int left = 1, right = numeric_limits<int>::max();
  while (left <= right) {
    int mid = left + ((right - left) >> 1); // 注意溢出，并且不能使用除法
    if (quickAdd(b, mid, a)) {
      ans = mid;
      if (mid == numeric_limits<int>::max()) { // 注意溢出
        break;
      }
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return rev ? -ans : ans;
}

int main() {
  std::cout << divide(4, 3) << std::endl;
  return 0;
}

package main

import "math"

// 快速乘
// x 和 y 是负数，z 是正数
// 判断 z * y >= x 是否成立
func QuickAdd(y, z, x int) bool {
	for result, add := 0, y; z > 0; z >>= 1 { // 不能使用除法
		if z&1 > 0 {
			// 需要保证 result + add >= x
			if result < x-add {
				return false
			}
			result += add
		}
		if z != 1 {
			// 需要保证 add + add >= x
			if add < x-add {
				return false
			}
			add += add
		}
	}
	return true
}

func divide(a, b int) int {
	if a == math.MinInt32 { // 考虑被除数为最小值的情况
		if b == 1 {
			return math.MinInt32
		}
		if b == -1 {
			return math.MaxInt32
		}
	}
	if b == math.MinInt32 { // 考虑除数为最小值的情况
		if a == math.MinInt32 {
			return 1
		}
		return 0
	}
	if a == 0 { // 考虑被除数为 0 的情况
		return 0
	}

	// 一般情况，使用二分查找
	// 将所有的正数取相反数，这样就只需要考虑一种情况
	rev := false
	if a > 0 {
		a = -a
		rev = !rev
	}
	if b > 0 {
		b = -b
		rev = !rev
	}

	ans := 0
	left, right := 1, math.MaxInt32
	for left <= right {
		mid := left + (right-left)>>1 // 注意溢出，并且不能使用除法
		if QuickAdd(b, mid, a) {
			ans = mid
			if mid == math.MaxInt32 { // 注意溢出
				break
			}
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	if rev {
		return -ans
	}
	return ans
}

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

// 二进制字符串相加
string addBinary(string a, string b) {
  string ans = "";
  int carry = 0;
  int lenA = a.size(), lenB = b.size();
  int n = max(lenA, lenB);

  // 从后往前逐位相加
  for (int i = 0; i < n; i++) {
    if (i < lenA) {
      carry += a[lenA - i - 1] - '0';
    }
    if (i < lenB) {
      carry += b[lenB - i - 1] - '0';
    }
    ans = char(carry % 2 + '0') + ans;
    carry /= 2;
  }

  // 如果最后有进位，补上一个1
  if (carry > 0) {
    ans = '1' + ans;
  }

  return ans;
}

int main() {
  std::cout << addBinary("11", "1") << std::endl;
  std::cout << addBinary("11", "1001") << std::endl;
  return 0;
}

package main

import "strconv"

func AddBinary(a string, b string) string {
	ans := ""
	carry := 0
	lenA, lenB := len(a), len(b)
	n := max(lenA, lenB)

	for i := 0; i < n; i++ {
		if i < lenA {
			carry += int(a[lenA-i-1] - '0')
		}
		if i < lenB {
			carry += int(b[lenB-i-1] - '0')
		}
		ans = strconv.Itoa(carry%2) + ans
		carry /= 2
	}
	if carry > 0 {
		ans = "1" + ans
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

#include <iostream>
#include <vector>
using namespace std;

// 计算一个整数的二进制表示中1的个数
int onesCount(int x) {
  int ones = 0;
  while (x > 0) {
    x &= (x - 1); // 消除最低位的1
    ones++;
  }
  return ones;
}

// 返回从0到n的每个整数的二进制表示中1的个数
vector<int> countBits(int n) {
  vector<int> bits(n + 1);
  for (int i = 0; i <= n; ++i) {
    bits[i] = onesCount(i);
  }
  return bits;
}

int main() {
  vector<int> bits = countBits(5);
  for (int i = 0; i < bits.size(); ++i) {
    cout << bits[i] << " ";
  }
  cout << endl;
  return 0;
}

package main

func onesCount(x int) (ones int) {
	for ; x > 0; x &= x - 1 {
		ones++
	}
	return
}

func CountBits(n int) []int {
	bits := make([]int, n+1)
	for i := range bits {
		bits[i] = onesCount(i)
	}
	return bits
}

#include <iostream>
#include <vector>
using namespace std;

int singleNumber(const vector<int>& nums) {
    int ans = 0;  // 32位整数，保存结果
    for (int i = 0; i < 32; ++i) {
        int total = 0;  // 记录第i位的1的个数
        for (int num : nums) {
            total += (num >> i) & 1;  // 取出num的第i位并累加
        }
        if (total % 3 > 0) {  // 如果该位上的1的个数不是3的倍数
            ans |= (1 << i);  // 将该位设置为1
        }
    }
    return ans;
}

int main() {
    vector<int> nums = { 1,1,1,2,2,2,3,3,3,4 };
    int ans = singleNumber(nums);
    cout << ans << endl;
    return 0;
}

package main

func SingleNumber(nums []int) int {
	ans := int32(0)
	for i := 0; i < 32; i++ {
		total := int32(0)
		for _, num := range nums {
			total += int32(num) >> i & 1
		}
		if total%3 > 0 {
			ans |= 1 << i
		}
	}
	return int(ans)
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int maxProduct(const vector<string> &words) {
  int ans = 0;
  int n = words.size();
  vector<int> masks(n, 0); // 用于存储每个单词的掩码

  // 计算每个单词的字母掩码
  for (int i = 0; i < n; ++i) {
    for (char ch : words[i]) {
      masks[i] |= (1 << (ch - 'a')); // 将字母对应的位标记为1
    }
  }

  // 两两比较掩码，找出没有公共字母的单词组合，并计算其乘积
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      if ((masks[i] & masks[j]) == 0) { // 判断是否没有公共字母
        int product = words[i].size() * words[j].size();
        if (product > ans) {
          ans = product;
        }
      }
    }
  }

  return ans;
}

int main() {
  vector<string> words = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"};
  int ans = maxProduct(words);
  cout << ans << endl;
  return 0;
}

package main

func MaxProduct(words []string) (ans int) {
	masks := make([]int, len(words))
	for i, word := range words {
		for _, ch := range word {
			masks[i] |= 1 << (ch - 'a')
		}
	}

	for i, x := range masks {
		for j, y := range masks[:i] {
			if x&y == 0 && len(words[i])*len(words[j]) > ans {
				ans = len(words[i]) * len(words[j])
			}
		}
	}
	return
}

#include <vector>

std::vector<int> TwoSum(const std::vector<int> &numbers, int target) {
  int low = 0, high = numbers.size() - 1;
  while (low < high) {
    int sum = numbers[low] + numbers[high];
    if (sum == target) {
      return {low, high};
    } else if (sum < target) {
      ++low;
    } else {
      --high;
    }
  }
  return {-1, -1};
}

package main

func TwoSum(numbers []int, target int) []int {
	low, high := 0, len(numbers)-1
	for low < high {
		sum := numbers[low] + numbers[high]
		if sum == target {
			return []int{low, high}
		} else if sum < target {
			low++
		} else {
			high--
		}
	}
	return []int{-1, -1}
}

#include <algorithm>
#include <vector>

std::vector<std::vector<int>> ThreeSum(std::vector<int> &nums) {
  std::vector<std::vector<int>> ans;
  std::sort(nums.begin(), nums.end());
  int n = nums.size();

  for (int first = 0; first < n; ++first) {
    if (first > 0 && nums[first] == nums[first - 1]) {
      continue;
    }
    int third = n - 1;
    int target = -nums[first];
    for (int second = first + 1; second < n; ++second) {
      if (second > first + 1 && nums[second] == nums[second - 1]) {
        continue;
      }
      while (second < third && nums[second] + nums[third] > target) {
        --third;
      }
      if (second == third) {
        break;
      }
      if (nums[second] + nums[third] == target) {
        ans.push_back({nums[first], nums[second], nums[third]});
      }
    }
  }
  return ans;
}

package main

import "sort"

func ThreeSum(nums []int) [][]int {
	n := len(nums)
	sort.Ints(nums)
	ans := make([][]int, 0)

	// 枚举 a
	for first := 0; first < n; first++ {
		// 需要和上一次枚举的数不相同
		if first > 0 && nums[first] == nums[first-1] {
			continue
		}
		// c 对应的指针初始指向数组的最右端
		third := n - 1
		target := -1 * nums[first]
		// 枚举 b
		for second := first + 1; second < n; second++ {
			// 需要和上一次枚举的数不相同
			if second > first+1 && nums[second] == nums[second-1] {
				continue
			}
			// 需要保证 b 的指针在 c 的指针的左侧
			for second < third && nums[second]+nums[third] > target {
				third--
			}
			// 如果指针重合，随着 b 后续的增加
			// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
			if second == third {
				break
			}
			if nums[second]+nums[third] == target {
				ans = append(ans, []int{nums[first], nums[second], nums[third]})
			}
		}
	}
	return ans
}

#include <algorithm>
#include <climits>
#include <vector>

int minSubArrayLen(int s, const std::vector<int> &nums) {
  int n = nums.size();
  if (n == 0) {
    return 0;
  }
  int ans = INT_MAX;
  int start = 0, end = 0, sum = 0;
  while (end < n) {
    sum += nums[end];
    while (sum >= s) {
      ans = std::min(ans, end - start + 1);
      sum -= nums[start];
      ++start;
    }
    ++end;
  }
  return (ans == INT_MAX) ? 0 : ans;
}

package main

import "math"

func MinSubArrayLen(s int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	ans := math.MaxInt32
	start, end := 0, 0
	sum := 0
	for end < n {
		sum += nums[end]
		for sum >= s {
			ans = min(ans, end-start+1)
			sum -= nums[start]
			start++
		}
		end++
	}
	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

#include <vector>

int numSubarrayProductLessThanK(const std::vector<int> &nums, int k) {
  if (k <= 1)
    return 0;
  int prod = 1, ans = 0, i = 0;
  for (int j = 0; j < nums.size(); ++j) {
    prod *= nums[j];
    while (prod >= k) {
      prod /= nums[i++];
    }
    ans += j - i + 1;
  }
  return ans;
}

package main

func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
	prod, i := 1, 0
	for j, num := range nums {
		prod *= num
		for ; i <= j && prod >= k; i++ {
			prod /= nums[i]
		}
		ans += j - i + 1
	}
	return
}

#include <unordered_map>
#include <vector>

int subarraySum(const std::vector<int> &nums, int k) {
  int count = 0, pre = 0;
  std::unordered_map<int, int> m;
  m[0] = 1;
  for (int i = 0; i < nums.size(); ++i) {
    pre += nums[i];
    if (m.find(pre - k) != m.end()) {
      count += m[pre - k];
    }
    m[pre]++;
  }
  return count;
}

package main

func subarraySum(nums []int, k int) int {
	count, pre := 0, 0
	m := map[int]int{}
	m[0] = 1
	for i := 0; i < len(nums); i++ {
		pre += nums[i]
		if _, ok := m[pre-k]; ok {
			count += m[pre-k]
		}
		m[pre] += 1
	}
	return count
}

#include <algorithm>
#include <unordered_map>
#include <vector>

int FindMaxLength(const std::vector<int> &nums) {
  std::unordered_map<int, int> mp = {{0, -1}};
  int maxLength = 0, counter = 0;
  for (int i = 0; i < nums.size(); ++i) {
    counter += (nums[i] == 1) ? 1 : -1;
    if (mp.find(counter) != mp.end()) {
      maxLength = std::max(maxLength, i - mp[counter]);
    } else {
      mp[counter] = i;
    }
  }
  return maxLength;
}

package main

func FindMaxLength(nums []int) (maxLength int) {
	mp := map[int]int{0: -1}
	counter := 0
	for i, num := range nums {
		if num == 1 {
			counter++
		} else {
			counter--
		}
		if prevIndex, has := mp[counter]; has {
			maxLength = max(maxLength, i-prevIndex)
		} else {
			mp[counter] = i
		}
	}
	return
}

#include <vector>

int pivotIndex(const std::vector<int> &nums) {
  int total = 0;
  for (int v : nums) {
    total += v;
  }
  int sum = 0;
  for (int i = 0; i < nums.size(); ++i) {
    if (2 * sum + nums[i] == total) {
      return i;
    }
    sum += nums[i];
  }
  return -1;
}

package main

func pivotIndex(nums []int) int {
	total := 0
	for _, v := range nums {
		total += v
	}
	sum := 0
	for i, v := range nums {
		if 2*sum+v == total {
			return i
		}
		sum += v
	}
	return -1
}

#include <vector>

class NumMatrix {
public:
  NumMatrix(const std::vector<std::vector<int>> &matrix) {
    int m = matrix.size();
    if (m == 0)
      return;
    int n = matrix[0].size();
    sums.resize(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        sums[i + 1][j + 1] =
            sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + matrix[i][j];
      }
    }
  }

  int SumRegion(int row1, int col1, int row2, int col2) {
    return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] -
           sums[row2 + 1][col1] + sums[row1][col1];
  }

private:
  std::vector<std::vector<int>> sums;
};

package main

type NumMatrix struct {
	sums [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	m := len(matrix)
	if m == 0 {
		return NumMatrix{}
	}
	n := len(matrix[0])
	sums := make([][]int, m+1)
	sums[0] = make([]int, n+1)
	for i, row := range matrix {
		sums[i+1] = make([]int, n+1)
		for j, v := range row {
			sums[i+1][j+1] = sums[i+1][j] + sums[i][j+1] - sums[i][j] + v
		}
	}
	return NumMatrix{sums}
}

func (nm *NumMatrix) SumRegion(row1, col1, row2, col2 int) int {
	return nm.sums[row2+1][col2+1] - nm.sums[row1][col2+1] - nm.sums[row2+1][col1] + nm.sums[row1][col1]
}

#include <string>
#include <vector>

bool checkInclusion(const std::string &s1, const std::string &s2) {
  int n = s1.size(), m = s2.size();
  if (n > m)
    return false;

  std::vector<int> cnt(26, 0);
  for (char ch : s1) {
    cnt[ch - 'a']--;
  }

  int left = 0;
  for (int right = 0; right < m; ++right) {
    int x = s2[right] - 'a';
    cnt[x]++;
    while (cnt[x] > 0) {
      cnt[s2[left] - 'a']--;
      left++;
    }
    if (right - left + 1 == n) {
      return true;
    }
  }
  return false;
}

package main

func checkInclusion(s1, s2 string) bool {
	n, m := len(s1), len(s2)
	if n > m {
		return false
	}
	cnt := [26]int{}
	for _, ch := range s1 {
		cnt[ch-'a']--
	}
	left := 0
	for right, ch := range s2 {
		x := ch - 'a'
		cnt[x]++
		for cnt[x] > 0 {
			cnt[s2[left]-'a']--
			left++
		}
		if right-left+1 == n {
			return true
		}
	}
	return false
}

#include <string>
#include <vector>

std::vector<int> findAnagrams(const std::string &s, const std::string &p) {
  std::vector<int> ans;
  int sLen = s.size(), pLen = p.size();
  if (sLen < pLen)
    return ans;

  std::vector<int> sCount(26, 0), pCount(26, 0);
  for (int i = 0; i < pLen; ++i) {
    sCount[s[i] - 'a']++;
    pCount[p[i] - 'a']++;
  }
  if (sCount == pCount) {
    ans.push_back(0);
  }

  for (int i = 0; i < sLen - pLen; ++i) {
    sCount[s[i] - 'a']--;
    sCount[s[i + pLen] - 'a']++;
    if (sCount == pCount) {
      ans.push_back(i + 1);
    }
  }
  return ans;
}

package main

func findAnagrams(s, p string) (ans []int) {
	sLen, pLen := len(s), len(p)
	if sLen < pLen {
		return
	}

	var sCount, pCount [26]int
	for i, ch := range p {
		sCount[s[i]-'a']++
		pCount[ch-'a']++
	}
	if sCount == pCount {
		ans = append(ans, 0)
	}

	for i, ch := range s[:sLen-pLen] {
		sCount[ch-'a']--
		sCount[s[i+pLen]-'a']++
		if sCount == pCount {
			ans = append(ans, i+1)
		}
	}
	return
}

#include <algorithm>
#include <string>
#include <unordered_map>

int lengthOfLongestSubstring(const std::string &s) {
  std::unordered_map<char, int> m;
  int n = s.length();
  int rk = -1, ans = 0;

  for (int i = 0; i < n; ++i) {
    if (i != 0) {
      m.erase(s[i - 1]);
    }
    while (rk + 1 < n && m[s[rk + 1]] == 0) {
      m[s[++rk]]++;
    }
    ans = std::max(ans, rk - i + 1);
  }

  return ans;
}

package main

func lengthOfLongestSubstring(s string) int {
	// 哈希集合，记录每个字符是否出现过
	m := map[byte]int{}
	n := len(s)
	// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
	rk, ans := -1, 0
	for i := 0; i < n; i++ {
		if i != 0 {
			// 左指针向右移动一格，移除一个字符
			delete(m, s[i-1])
		}
		for rk+1 < n && m[s[rk+1]] == 0 {
			// 不断地移动右指针
			m[s[rk+1]]++
			rk++
		}
		// 第 i 到 rk 个字符是一个极长的无重复字符子串
		ans = max(ans, rk-i+1)
	}
	return ans
}

#include <climits>
#include <string>
#include <unordered_map>

std::string minWindow(const std::string &s, const std::string &t) {
  std::unordered_map<char, int> ori, cnt;
  for (char c : t) {
    ori[c]++;
  }

  int sLen = s.length();
  int minLen = INT_MAX;
  int ansL = -1, ansR = -1;

  auto check = [&]() -> bool {
    for (const auto &[k, v] : ori) {
      if (cnt[k] < v) {
        return false;
      }
    }
    return true;
  };

  for (int l = 0, r = 0; r < sLen; ++r) {
    if (ori.find(s[r]) != ori.end()) {
      cnt[s[r]]++;
    }
    while (check() && l <= r) {
      if (r - l + 1 < minLen) {
        minLen = r - l + 1;
        ansL = l;
        ansR = l + minLen;
      }
      if (ori.find(s[l]) != ori.end()) {
        cnt[s[l]]--;
      }
      ++l;
    }
  }

  if (ansL == -1) {
    return "";
  }
  return s.substr(ansL, ansR - ansL);
}

package main

import "math"

func minWindow(s string, t string) string {
	ori, cnt := map[byte]int{}, map[byte]int{}
	for i := 0; i < len(t); i++ {
		ori[t[i]]++
	}

	sLen := len(s)
	len := math.MaxInt32
	ansL, ansR := -1, -1

	check := func() bool {
		for k, v := range ori {
			if cnt[k] < v {
				return false
			}
		}
		return true
	}
	for l, r := 0, 0; r < sLen; r++ {
		if r < sLen && ori[s[r]] > 0 {
			cnt[s[r]]++
		}
		for check() && l <= r {
			if r-l+1 < len {
				len = r - l + 1
				ansL, ansR = l, l+len
			}
			if _, ok := ori[s[l]]; ok {
				cnt[s[l]] -= 1
			}
			l++
		}
	}
	if ansL == -1 {
		return ""
	}
	return s[ansL:ansR]
}

#include <algorithm>
#include <cctype>
#include <string>

bool isalnum(char ch) {
  return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') ||
         (ch >= '0' && ch <= '9');
}

bool isPalindrome(const std::string &s) {
  std::string sgood;
  for (char ch : s) {
    if (isalnum(ch)) {
      sgood += std::tolower(ch);
    }
  }

  int n = sgood.length();
  for (int i = 0; i < n / 2; ++i) {
    if (sgood[i] != sgood[n - 1 - i]) {
      return false;
    }
  }
  return true;
}

package main

import "strings"

func isPalindrome(s string) bool {
	var sgood string
	for i := 0; i < len(s); i++ {
		if isalnum(s[i]) {
			sgood += string(s[i])
		}
	}

	n := len(sgood)
	sgood = strings.ToLower(sgood)
	for i := 0; i < n/2; i++ {
		if sgood[i] != sgood[n-1-i] {
			return false
		}
	}
	return true
}

func isalnum(ch byte) bool {
	return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}

#include <string>

bool validPalindrome(const std::string &s) {
  int low = 0, high = s.length() - 1;
  while (low < high) {
    if (s[low] == s[high]) {
      ++low;
      --high;
    } else {
      bool flag1 = true, flag2 = true;
      for (int i = low, j = high - 1; i < j; ++i, --j) {
        if (s[i] != s[j]) {
          flag1 = false;
          break;
        }
      }
      for (int i = low + 1, j = high; i < j; ++i, --j) {
        if (s[i] != s[j]) {
          flag2 = false;
          break;
        }
      }
      return flag1 || flag2;
    }
  }
  return true;
}

package main

func validPalindrome(s string) bool {
	low, high := 0, len(s)-1
	for low < high {
		if s[low] == s[high] {
			low++
			high--
		} else {
			flag1, flag2 := true, true
			for i, j := low, high-1; i < j; i, j = i+1, j-1 {
				if s[i] != s[j] {
					flag1 = false
					break
				}
			}
			for i, j := low+1, high; i < j; i, j = i+1, j-1 {
				if s[i] != s[j] {
					flag2 = false
					break
				}
			}
			return flag1 || flag2
		}
	}
	return true
}

#include <string>

int countSubstrings(const std::string &s) {
  int n = s.length();
  int ans = 0;
  for (int i = 0; i < 2 * n - 1; ++i) {
    int l = i / 2;
    int r = i / 2 + i % 2;
    while (l >= 0 && r < n && s[l] == s[r]) {
      --l;
      ++r;
      ++ans;
    }
  }
  return ans;
}

package main

func countSubstrings(s string) int {
	n := len(s)
	ans := 0
	for i := 0; i < 2*n-1; i++ {
		l, r := i/2, i/2+i%2
		for l >= 0 && r < n && s[l] == s[r] {
			l--
			r++
			ans++
		}
	}
	return ans
}

struct ListNode {
  int Val;
  ListNode *Next;
  ListNode(int x) : Val(x), Next(nullptr) {}
};

ListNode *removeNthFromEnd(ListNode *head, int n) {
  ListNode *dummy = new ListNode(0);
  dummy->Next = head;
  ListNode *first = head;
  ListNode *second = dummy;

  for (int i = 0; i < n; ++i) {
    first = first->Next;
  }

  while (first != nullptr) {
    first = first->Next;
    second = second->Next;
  }

  second->Next = second->Next->Next;
  ListNode *newHead = dummy->Next;
  delete dummy; // Free the allocated memory for dummy node
  return newHead;
}

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{0, head}
	first, second := head, dummy
	for i := 0; i < n; i++ {
		first = first.Next
	}
	for ; first != nil; first = first.Next {
		second = second.Next
	}
	second.Next = second.Next.Next
	return dummy.Next
}

struct ListNode {
  int Val;
  ListNode *Next;
  ListNode(int x) : Val(x), Next(nullptr) {}
};

ListNode *detectCycle(ListNode *head) {
  if (!head)
    return nullptr;

  ListNode *slow = head;
  ListNode *fast = head;

  while (fast != nullptr && fast->Next != nullptr) {
    slow = slow->Next;
    fast = fast->Next->Next;

    if (slow == fast) {
      ListNode *p = head;
      while (p != slow) {
        p = p->Next;
        slow = slow->Next;
      }
      return p;
    }
  }

  return nullptr;
}

package main

func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil {
		slow = slow.Next
		if fast.Next == nil {
			return nil
		}
		fast = fast.Next.Next
		if fast == slow {
			p := head
			for p != slow {
				p = p.Next
				slow = slow.Next
			}
			return p
		}
	}
	return nil
}

struct ListNode {
  int Val;
  ListNode *Next;
  ListNode(int x) : Val(x), Next(nullptr) {}
};

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  if (headA == nullptr || headB == nullptr) {
    return nullptr;
  }

  ListNode *pa = headA;
  ListNode *pb = headB;

  while (pa != pb) {
    pa = (pa == nullptr) ? headB : pa->Next;
    pb = (pb == nullptr) ? headA : pb->Next;
  }

  return pa;
}

package main

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	pa, pb := headA, headB
	for pa != pb {
		if pa == nil {
			pa = headB
		} else {
			pa = pa.Next
		}
		if pb == nil {
			pb = headA
		} else {
			pb = pb.Next
		}
	}
	return pa
}

struct ListNode {
  int Val;
  ListNode *Next;
  ListNode(int x) : Val(x), Next(nullptr) {}
};

ListNode *reverseList(ListNode *head) {
  if (head == nullptr || head->Next == nullptr) {
    return head;
  }
  ListNode *newHead = reverseList(head->Next);
  head->Next->Next = head;
  head->Next = nullptr;
  return newHead;
}

package main

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

#include <vector>

struct ListNode {
  int Val;
  ListNode *Next;
  ListNode(int x) : Val(x), Next(nullptr) {}
};

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
  std::vector<int> s1, s2;
  while (l1 != nullptr) {
    s1.push_back(l1->Val);
    l1 = l1->Next;
  }
  while (l2 != nullptr) {
    s2.push_back(l2->Val);
    l2 = l2->Next;
  }

  int carry = 0;
  ListNode *head = nullptr;
  while (!s1.empty() || !s2.empty() || carry != 0) {
    int sum = 0;
    if (!s1.empty()) {
      sum += s1.back();
      s1.pop_back();
    }
    if (!s2.empty()) {
      sum += s2.back();
      s2.pop_back();
    }
    sum += carry;
    ListNode *node = new ListNode(sum % 10);
    node->Next = head;
    head = node;
    carry = sum / 10;
  }

  return head;
}

package main

func addTwoNumbers(l1 *ListNode, l2 *ListNode) (head *ListNode) {
	var s1, s2 []int
	for l1 != nil {
		s1 = append(s1, l1.Val)
		l1 = l1.Next
	}
	for l2 != nil {
		s2 = append(s2, l2.Val)
		l2 = l2.Next
	}
	carry := 0
	for len(s1) > 0 || len(s2) > 0 || carry > 0 {
		sum := 0
		if len(s1) > 0 {
			sum += s1[len(s1)-1]
			s1 = s1[:len(s1)-1]
		}
		if len(s2) > 0 {
			sum += s2[len(s2)-1]
			s2 = s2[:len(s2)-1]
		}
		sum += carry
		node := &ListNode{Val: sum % 10}
		node.Next = head
		head = node
		carry = sum / 10
	}
	return
}

#include <vector>

struct ListNode {
  int Val;
  ListNode *Next;
  ListNode(int x) : Val(x), Next(nullptr) {}
};

void reorderList(ListNode *head) {
  if (head == nullptr) {
    return;
  }

  std::vector<ListNode *> nodes;
  for (ListNode *node = head; node != nullptr; node = node->Next) {
    nodes.push_back(node);
  }

  int i = 0, j = nodes.size() - 1;
  while (i < j) {
    nodes[i]->Next = nodes[j];
    ++i;
    if (i == j) {
      break;
    }
    nodes[j]->Next = nodes[i];
    --j;
  }
  nodes[i]->Next = nullptr;
}

package main

func reorderList(head *ListNode) {
	if head == nil {
		return
	}
	nodes := []*ListNode{}
	for node := head; node != nil; node = node.Next {
		nodes = append(nodes, node)
	}
	i, j := 0, len(nodes)-1
	for i < j {
		nodes[i].Next = nodes[j]
		i++
		if i == j {
			break
		}
		nodes[j].Next = nodes[i]
		j--
	}
	nodes[i].Next = nil
}

#include <vector>

struct ListNode {
  int Val;
  ListNode *Next;
  ListNode(int x) : Val(x), Next(nullptr) {}
};

bool isLinkListPalindrome(ListNode *head) {
  std::vector<int> vals;
  for (ListNode *node = head; node != nullptr; node = node->Next) {
    vals.push_back(node->Val);
  }

  int n = vals.size();
  for (int i = 0; i < n / 2; ++i) {
    if (vals[i] != vals[n - 1 - i]) {
      return false;
    }
  }
  return true;
}

package main

func isLinkListPalindrome(head *ListNode) bool {
	vals := []int{}
	for ; head != nil; head = head.Next {
		vals = append(vals, head.Val)
	}
	n := len(vals)
	for i, v := range vals[:n/2] {
		if v != vals[n-1-i] {
			return false
		}
	}
	return true
}

struct Node {
  int Val;
  Node *Prev;
  Node *Next;
  Node *Child;
  Node(int x) : Val(x), Prev(nullptr), Next(nullptr), Child(nullptr) {}
};

Node *dfs(Node *node) {
  Node *cur = node;
  Node *last = nullptr;

  while (cur != nullptr) {
    Node *next = cur->Next;
    if (cur->Child != nullptr) {
      Node *childLast = dfs(cur->Child);

      cur->Next = cur->Child;
      cur->Child->Prev = cur;

      if (next != nullptr) {
        childLast->Next = next;
        next->Prev = childLast;
      }

      cur->Child = nullptr;
      last = childLast;
    } else {
      last = cur;
    }
    cur = next;
  }
  return last;
}

Node *flatten(Node *root) {
  dfs(root);
  return root;
}

package main

type LinkNode struct {
	Val   int
	Next  *LinkNode
	Prev  *LinkNode
	Child *LinkNode
}

func dfs(node *LinkNode) (last *LinkNode) {
	cur := node
	for cur != nil {
		next := cur.Next
		// 如果有子节点，那么首先处理子节点
		if cur.Child != nil {
			childLast := dfs(cur.Child)

			next = cur.Next
			// 将 node 与 child 相连
			cur.Next = cur.Child
			cur.Child.Prev = cur

			// 如果 next 不为空，就将 last 与 next 相连
			if next != nil {
				childLast.Next = next
				next.Prev = childLast
			}

			// 将 child 置为空
			cur.Child = nil
			last = childLast
		} else {
			last = cur
		}
		cur = next
	}
	return
}

func flatten(root *LinkNode) *LinkNode {
	dfs(root)
	return root
}

struct Node {
  int Val;
  Node *Next;
  Node(int x) : Val(x), Next(nullptr) {}
};

Node *insert(Node *head, int insertVal) {
  Node *node = new Node(insertVal);
  if (head == nullptr) {
    node->Next = node;
    return node;
  }
  if (head->Next == head) {
    head->Next = node;
    node->Next = head;
    return head;
  }
  Node *curr = head;
  Node *next = head->Next;
  while (next != head) {
    if (insertVal >= curr->Val && insertVal <= next->Val) {
      break;
    }
    if (curr->Val > next->Val) {
      if (insertVal > curr->Val || insertVal < next->Val) {
        break;
      }
    }
    curr = curr->Next;
    next = next->Next;
  }
  curr->Next = node;
  node->Next = next;
  return head;
}

package main

func insert(head *ListNode, insertVal int) *ListNode {
	node := &ListNode{Val: insertVal}
	if head == nil {
		node.Next = node
		return node
	}
	if head.Next == head {
		head.Next = node
		node.Next = head
		return head
	}
	curr, next := head, head.Next
	for next != head {
		if insertVal >= curr.Val && insertVal <= next.Val {
			break
		}
		if curr.Val > next.Val {
			if insertVal > curr.Val || insertVal < next.Val {
				break
			}
		}
		curr = curr.Next
		next = next.Next
	}
	curr.Next = node
	node.Next = next
	return head
}

#include <cstdlib>
#include <unordered_map>
#include <vector>

class RandomizedSet {
public:
  RandomizedSet() {}

  bool insert(int val) {
    if (indices.find(val) != indices.end()) {
      return false;
    }
    indices[val] = nums.size();
    nums.push_back(val);
    return true;
  }

  bool remove(int val) {
    auto it = indices.find(val);
    if (it == indices.end()) {
      return false;
    }
    int last = nums.back();
    nums[it->second] = last;
    indices[last] = it->second;
    nums.pop_back();
    indices.erase(val);
    return true;
  }

  int getRandom() {
    int randomIndex = rand() % nums.size();
    return nums[randomIndex];
  }

private:
  std::vector<int> nums;
  std::unordered_map<int, int> indices;
};

package main

import "math/rand"

type RandomizedSet struct {
	nums    []int
	indices map[int]int
}

func NewRandomizedSet() RandomizedSet {
	return RandomizedSet{
		[]int{}, map[int]int{},
	}
}

func (rs *RandomizedSet) Insert(val int) bool {
	if _, ok := rs.indices[val]; ok {
		return false
	}
	rs.indices[val] = len(rs.nums)
	rs.nums = append(rs.nums, val)
	return true
}

func (rs *RandomizedSet) Remove(val int) bool {
	id, ok := rs.indices[val]
	if !ok {
		return false
	}
	last := len(rs.nums) - 1
	rs.nums[id] = rs.nums[last]
	rs.indices[rs.nums[id]] = id
	rs.nums = rs.nums[:last]
	delete(rs.indices, val)
	return true
}

func (rs *RandomizedSet) GetRandom() int {
	return rs.nums[rand.Intn(len(rs.nums))]
}

#include <list>
#include <unordered_map>

class LRUCache {
public:
  LRUCache(int capacity) : capacity(capacity) {}

  int get(int key) {
    auto it = cache.find(key);
    if (it == cache.end()) {
      return -1;
    }
    // Move the accessed element to the front of the list
    list.splice(list.begin(), list, it->second);
    return it->second->second;
  }

  void put(int key, int value) {
    auto it = cache.find(key);
    if (it != cache.end()) {
      // Update the value and move the element to the front of the list
      it->second->second = value;
      list.splice(list.begin(), list, it->second);
      return;
    }
    if (list.size() == capacity) {
      // Remove the least recently used element
      int lruKey = list.back().first;
      list.pop_back();
      cache.erase(lruKey);
    }
    // Insert the new element at the front of the list
    list.emplace_front(key, value);
    cache[key] = list.begin();
  }

private:
  int capacity;
  std::list<std::pair<int, int>> list;
  std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache;
};

package main

import "container/list"

type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	list     *list.List
}

type entry struct {
	key   int
	value int
}

func NewLRUCache(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*list.Element),
		list:     list.New(),
	}
}

func (this *LRUCache) Get(key int) int {
	if elem, ok := this.cache[key]; ok {
		this.list.MoveToFront(elem)
		return elem.Value.(*entry).value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if elem, ok := this.cache[key]; ok {
		elem.Value.(*entry).value = value
		this.list.MoveToFront(elem)
		return
	}
	if this.list.Len() == this.capacity {
		lastElem := this.list.Back()
		delete(this.cache, lastElem.Value.(*entry).key)
		this.list.Remove(lastElem)
	}
	newElem := this.list.PushFront(&entry{key: key, value: value})
	this.cache[key] = newElem
}

#include <string>
#include <vector>

bool isAnagram(const std::string &s, const std::string &t) {
  if (s == t) {
    return false;
  }
  std::vector<int> c1(26, 0), c2(26, 0);
  for (char ch : s) {
    c1[ch - 'a']++;
  }
  for (char ch : t) {
    c2[ch - 'a']++;
  }
  return c1 == c2;
}

package main

func isAnagram(s, t string) bool {
	if s == t {
		return false
	}
	var c1, c2 [26]int
	for _, ch := range s {
		c1[ch-'a']++
	}
	for _, ch := range t {
		c2[ch-'a']++
	}
	return c1 == c2
}

#include <array>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<std::vector<std::string>>
groupAnagrams(std::vector<std::string> &strs) {
  std::unordered_map<std::array<int, 26>, std::vector<std::string>> mp;
  for (const auto &str : strs) {
    std::array<int, 26> cnt = {0};
    for (char ch : str) {
      cnt[ch - 'a']++;
    }
    mp[cnt].push_back(str);
  }
  std::vector<std::vector<std::string>> ans;
  for (auto &[key, group] : mp) {
    ans.push_back(std::move(group));
  }
  return ans;
}

package main

func groupAnagrams(strs []string) [][]string {
	mp := map[[26]int][]string{}
	for _, str := range strs {
		cnt := [26]int{}
		for _, b := range str {
			cnt[b-'a']++
		}
		mp[cnt] = append(mp[cnt], str)
	}
	ans := make([][]string, 0, len(mp))
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

#include <string>
#include <unordered_map>
#include <vector>

bool isAlienSorted(const std::vector<std::string> &words,
                   const std::string &order) {
  std::vector<int> index(26, 0);
  for (int i = 0; i < order.size(); ++i) {
    index[order[i] - 'a'] = i;
  }

  for (int i = 1; i < words.size(); ++i) {
    const std::string &prev = words[i - 1];
    const std::string &curr = words[i];
    for (int j = 0; j < std::min(prev.size(), curr.size()); ++j) {
      int pre = index[prev[j] - 'a'];
      int cur = index[curr[j] - 'a'];
      if (pre > cur) {
        return false;
      }
      if (pre < cur) {
        goto next_word;
      }
    }
    if (prev.size() > curr.size()) {
      return false;
    }
  next_word:;
  }
  return true;
}

package main

func isAlienSorted(words []string, order string) bool {
	index := [26]int{}
	for i, c := range order {
		index[c-'a'] = i
	}
next:
	for i := 1; i < len(words); i++ {
		for j := 0; j < len(words[i-1]) && j < len(words[i]); j++ {
			pre, cur := index[words[i-1][j]-'a'], index[words[i][j]-'a']
			if pre > cur {
				return false
			}
			if pre < cur {
				continue next
			}
		}
		if len(words[i-1]) > len(words[i]) {
			return false
		}
	}
	return true
}

#include <algorithm>
#include <climits>
#include <string>
#include <vector>

int getMinutes(const std::string &t) {
  return (t[0] - '0') * 10 * 60 + (t[1] - '0') * 60 + (t[3] - '0') * 10 +
         (t[4] - '0');
}

int findMinDifference(std::vector<std::string> &timePoints) {
  if (timePoints.size() > 1440) {
    return 0;
  }
  std::sort(timePoints.begin(), timePoints.end());
  int ans = INT_MAX;
  int t0Minutes = getMinutes(timePoints[0]);
  int preMinutes = t0Minutes;
  for (int i = 1; i < timePoints.size(); ++i) {
    int minutes = getMinutes(timePoints[i]);
    ans = std::min(ans,
                   minutes - preMinutes); // Difference between adjacent times
    preMinutes = minutes;
  }
  ans = std::min(ans,
                 t0Minutes + 1440 -
                     preMinutes); // Difference between the first and last time
  return ans;
}

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

package main

import (
	"math"
	"sort"
)

func getMinutes(t string) int {
	return (int(t[0]-'0')*10+int(t[1]-'0'))*60 + int(t[3]-'0')*10 + int(t[4]-'0')
}

func findMinDifference(timePoints []string) int {
	if len(timePoints) > 1440 {
		return 0
	}
	sort.Strings(timePoints)
	ans := math.MaxInt32
	t0Minutes := getMinutes(timePoints[0])
	preMinutes := t0Minutes
	for _, t := range timePoints[1:] {
		minutes := getMinutes(t)
		ans = min(ans, minutes-preMinutes) // 相邻时间的时间差
		preMinutes = minutes
	}
	ans = min(ans, t0Minutes+1440-preMinutes) // 首尾时间的时间差
	return ans
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

#include <stack>
#include <stdexcept>
#include <string>
#include <vector>

int evalRPN(const std::vector<std::string> &tokens) {
  std::stack<int> stack;
  for (const auto &token : tokens) {
    if (isdigit(token.back())) {
      stack.push(std::stoi(token));
    } else {
      int b = stack.top();
      stack.pop();
      int a = stack.top();
      stack.pop();
      if (token == "+") {
        stack.push(a + b);
      } else if (token == "-") {
        stack.push(a - b);
      } else if (token == "*") {
        stack.push(a * b);
      } else if (token == "/") {
        stack.push(a / b);
      } else {
        throw std::invalid_argument("Invalid operator");
      }
    }
  }
  return stack.top();
}

package main

import "strconv"

func evalRPN(tokens []string) int {
	stack := make([]int, (len(tokens)+1)/2)
	index := -1
	for _, token := range tokens {
		val, err := strconv.Atoi(token)
		if err == nil {
			index++
			stack[index] = val
		} else {
			index--
			switch token {
			case "+":
				stack[index] += stack[index+1]
			case "-":
				stack[index] -= stack[index+1]
			case "*":
				stack[index] *= stack[index+1]
			default:
				stack[index] /= stack[index+1]
			}
		}
	}
	return stack[0]
}

#include <vector>

std::vector<int> asteroidCollision(const std::vector<int> &asteroids) {
  std::vector<int> st;
  for (int aster : asteroids) {
    bool alive = true;
    while (alive && aster < 0 && !st.empty() && st.back() > 0) {
      alive = st.back() < -aster; // Check if the current asteroid survives
      if (st.back() <= -aster) {  // Top of the stack asteroid explodes
        st.pop_back();
      }
    }
    if (alive) {
      st.push_back(aster);
    }
  }
  return st;
}

package main

func asteroidCollision(asteroids []int) (st []int) {
	for _, aster := range asteroids {
		alive := true
		for alive && aster < 0 && len(st) > 0 && st[len(st)-1] > 0 {
			alive = st[len(st)-1] < -aster // aster 是否存在
			if st[len(st)-1] <= -aster {   // 栈顶小行星爆炸
				st = st[:len(st)-1]
			}
		}
		if alive {
			st = append(st, aster)
		}
	}
	return
}

#include <stack>
#include <vector>

std::vector<int> dailyTemperatures(const std::vector<int> &temperatures) {
  int length = temperatures.size();
  std::vector<int> ans(length, 0);
  std::stack<int> stack;

  for (int i = 0; i < length; ++i) {
    int temperature = temperatures[i];
    while (!stack.empty() && temperature > temperatures[stack.top()]) {
      int prevIndex = stack.top();
      stack.pop();
      ans[prevIndex] = i - prevIndex;
    }
    stack.push(i);
  }

  return ans;
}

package main

func dailyTemperatures(temperatures []int) []int {
	length := len(temperatures)
	ans := make([]int, length)
	stack := []int{}
	for i := 0; i < length; i++ {
		temperature := temperatures[i]
		for len(stack) > 0 && temperature > temperatures[stack[len(stack)-1]] {
			prevIndex := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans[prevIndex] = i - prevIndex
		}
		stack = append(stack, i)
	}
	return ans
}

#include <algorithm>
#include <stack>
#include <vector>

int largestRectangleArea(const std::vector<int> &heights) {
  int n = heights.size();
  std::vector<int> left(n), right(n);
  std::stack<int> mono_stack;

  for (int i = 0; i < n; ++i) {
    while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
      mono_stack.pop();
    }
    left[i] = mono_stack.empty() ? -1 : mono_stack.top();
    mono_stack.push(i);
  }

  while (!mono_stack.empty())
    mono_stack.pop();

  for (int i = n - 1; i >= 0; --i) {
    while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
      mono_stack.pop();
    }
    right[i] = mono_stack.empty() ? n : mono_stack.top();
    mono_stack.push(i);
  }

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    ans = std::max(ans, (right[i] - left[i] - 1) * heights[i]);
  }

  return ans;
}

int max(int x, int y) { return x > y ? x : y; }

package main

func largestRectangleArea(heights []int) int {
	n := len(heights)
	left, right := make([]int, n), make([]int, n)
	mono_stack := []int{}
	for i := 0; i < n; i++ {
		for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {
			mono_stack = mono_stack[:len(mono_stack)-1]
		}
		if len(mono_stack) == 0 {
			left[i] = -1
		} else {
			left[i] = mono_stack[len(mono_stack)-1]
		}
		mono_stack = append(mono_stack, i)
	}
	mono_stack = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {
			mono_stack = mono_stack[:len(mono_stack)-1]
		}
		if len(mono_stack) == 0 {
			right[i] = n
		} else {
			right[i] = mono_stack[len(mono_stack)-1]
		}
		mono_stack = append(mono_stack, i)
	}
	ans := 0
	for i := 0; i < n; i++ {
		ans = max(ans, (right[i]-left[i]-1)*heights[i])
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int maximalRectangle(vector<string> &matrix) {
  if (matrix.empty()) {
    return 0;
  }
  int m = matrix.size(), n = matrix[0].size();
  vector<vector<int>> left(m, vector<int>(n, 0));
  int ans = 0;

  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if (matrix[i][j] == '0') {
        continue;
      }
      if (j == 0) {
        left[i][j] = 1;
      } else {
        left[i][j] = left[i][j - 1] + 1;
      }
    }
  }

  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if (matrix[i][j] == '0') {
        continue;
      }
      int width = left[i][j];
      int area = width;
      for (int k = i - 1; k >= 0; --k) {
        width = min(width, left[k][j]);
        if (width == 0) {
          break;
        }
        area = max(area, (i - k + 1) * width);
      }
      ans = max(ans, area);
    }
  }

  return ans;
}

package main

func maximalRectangle(matrix []string) (ans int) {
	if len(matrix) == 0 {
		return
	}
	m, n := len(matrix), len(matrix[0])
	left := make([][]int, m)
	for i, row := range matrix {
		left[i] = make([]int, n)
		for j, v := range row {
			if v == '0' {
				continue
			}
			if j == 0 {
				left[i][j] = 1
			} else {
				left[i][j] = left[i][j-1] + 1
			}
		}
	}
	for i, row := range matrix {
		for j, v := range row {
			if v == '0' {
				continue
			}
			width := left[i][j]
			area := width
			for k := i - 1; k >= 0; k-- {
				width = min(width, left[k][j])
				if width == 0 {
					break
				}
				area = max(area, (i-k+1)*width)
			}
			ans = max(ans, area)
		}
	}
	return
}

#include <vector>

class MovingAverage {
public:
  MovingAverage(int size) : size(size), sum(0) {}

  double next(int val) {
    if (q.size() == size) {
      sum -= q.front();
      q.erase(q.begin());
    }
    sum += val;
    q.push_back(val);
    return static_cast<double>(sum) / q.size();
  }

private:
  int size;
  int sum;
  std::vector<int> q;
};

package main

type MovingAverage struct {
	size, sum int
	q         []int
}

func Constructor(size int) MovingAverage {
	return MovingAverage{size: size}
}

func (m *MovingAverage) Next(val int) float64 {
	if len(m.q) == m.size {
		m.sum -= m.q[0]
		m.q = m.q[1:]
	}
	m.sum += val
	m.q = append(m.q, val)
	return float64(m.sum) / float64(len(m.q))
}

#include <deque>

class RecentCounter {
public:
  RecentCounter() {}

  int ping(int t) {
    q.push_back(t);
    while (q.front() < t - 3000) {
      q.pop_front();
    }
    return q.size();
  }

private:
  std::deque<int> q;
};

package main

type RecentCounter []int

func NewRecentCounter() (_ RecentCounter) { return }

func (q *RecentCounter) Ping(t int) int {
	*q = append(*q, t)
	for (*q)[0] < t-3000 {
		*q = (*q)[1:]
	}
	return len(*q)
}

#include <queue>
#include <vector>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class CBTInserter {
public:
  CBTInserter(TreeNode *root) : root(root) {
    std::queue<TreeNode *> q;
    q.push(root);
    while (!q.empty()) {
      TreeNode *node = q.front();
      q.pop();
      if (node->left) {
        q.push(node->left);
      }
      if (node->right) {
        q.push(node->right);
      }
      if (!node->left || !node->right) {
        candidate.push_back(node);
      }
    }
  }

  int insert(int val) {
    TreeNode *child = new TreeNode(val);
    TreeNode *node = candidate.front();
    if (!node->left) {
      node->left = child;
    } else {
      node->right = child;
      candidate.erase(candidate.begin());
    }
    candidate.push_back(child);
    return node->val;
  }

  TreeNode *get_root() { return root; }

private:
  TreeNode *root;
  std::vector<TreeNode *> candidate;
};

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type CBTInserter struct {
	root      *TreeNode
	candidate []*TreeNode
}

func NewCBT(root *TreeNode) CBTInserter {
	q := []*TreeNode{root}
	candidate := []*TreeNode{}
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		if node.Left != nil {
			q = append(q, node.Left)
		}
		if node.Right != nil {
			q = append(q, node.Right)
		}
		if node.Left == nil || node.Right == nil {
			candidate = append(candidate, node)
		}
	}
	return CBTInserter{root, candidate}
}

func (c *CBTInserter) Insert(val int) int {
	child := &TreeNode{Val: val}
	node := c.candidate[0]
	if node.Left == nil {
		node.Left = child
	} else {
		node.Right = child
		c.candidate = c.candidate[1:]
	}
	c.candidate = append(c.candidate, child)
	return node.Val
}

func (c *CBTInserter) Get_root() *TreeNode {
	return c.root
}

#include <algorithm>
#include <vector>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  std::vector<int> largestValues(TreeNode *root) {
    std::vector<int> ans;
    dfs(root, 0, ans);
    return ans;
  }

private:
  void dfs(TreeNode *node, int curHeight, std::vector<int> &ans) {
    if (!node) {
      return;
    }
    if (curHeight == ans.size()) {
      ans.push_back(node->val);
    } else {
      ans[curHeight] = std::max(ans[curHeight], node->val);
    }
    dfs(node->left, curHeight + 1, ans);
    dfs(node->right, curHeight + 1, ans);
  }
};

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

package main

func largestValues(root *TreeNode) (ans []int) {
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, curHeight int) {
		if node == nil {
			return
		}
		if curHeight == len(ans) {
			ans = append(ans, node.Val)
		} else {
			ans[curHeight] = max(ans[curHeight], node.Val)
		}
		dfs(node.Left, curHeight+1)
		dfs(node.Right, curHeight+1)
	}
	dfs(root, 0)
	return
}

#include <algorithm>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  int findBottomLeftValue(TreeNode *root) {
    int curVal = 0;
    int curHeight = 0;
    dfs(root, 0, curHeight, curVal);
    return curVal;
  }

private:
  void dfs(TreeNode *node, int height, int &curHeight, int &curVal) {
    if (!node) {
      return;
    }
    height++;
    dfs(node->left, height, curHeight, curVal);
    dfs(node->right, height, curHeight, curVal);
    if (height > curHeight) {
      curHeight = height;
      curVal = node->val;
    }
  }
};

package main

func findBottomLeftValue(root *TreeNode) (curVal int) {
	curHeight := 0
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, height int) {
		if node == nil {
			return
		}
		height++
		dfs(node.Left, height)
		dfs(node.Right, height)
		if height > curHeight {
			curHeight = height
			curVal = node.Val
		}
	}
	dfs(root, 0)
	return
}

#include <vector>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  std::vector<int> rightSideView(TreeNode *root) {
    std::vector<int> ans;
    if (!root) {
      return ans;
    }
    dfs(root, 0, ans);
    return ans;
  }

private:
  void dfs(TreeNode *node, int depth, std::vector<int> &ans) {
    if (!node) {
      return;
    }
    if (depth == ans.size()) {
      ans.push_back(node->val);
    }
    dfs(node->right, depth + 1, ans);
    dfs(node->left, depth + 1, ans);
  }
};

package main

func rightSideView(root *TreeNode) []int {
	ans := []int{}
	if root == nil {
		return ans
	}
	var dfs func(node *TreeNode, depth int)
	dfs = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}

		if len(ans) == depth {
			ans = append(ans, node.Val)
		}
		dfs(node.Right, depth+1)
		dfs(node.Left, depth+1)
	}
	dfs(root, 0)
	return ans
}

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  TreeNode *pruneTree(TreeNode *root) {
    if (!root) {
      return nullptr;
    }
    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);
    if (!root->left && !root->right && root->val == 0) {
      return nullptr;
    }
    return root;
  }
};

package main

func pruneTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left = pruneTree(root.Left)
	root.Right = pruneTree(root.Right)
	if root.Left == nil && root.Right == nil && root.Val == 0 {
		return nil
	}
	return root
}

#include <queue>
#include <sstream>
#include <string>
#include <vector>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
  // Serializes a tree to a single string.
  std::string serialize(TreeNode *root) {
    std::ostringstream sb;
    serializeHelper(root, sb);
    return sb.str();
  }

  // Deserializes your encoded data to tree.
  TreeNode *deserialize(const std::string &data) {
    std::vector<std::string> nodes = split(data, ',');
    int index = 0;
    return deserializeHelper(nodes, index);
  }

private:
  void serializeHelper(TreeNode *node, std::ostringstream &sb) {
    if (!node) {
      sb << "null,";
      return;
    }
    sb << node->val << ',';
    serializeHelper(node->left, sb);
    serializeHelper(node->right, sb);
  }

  TreeNode *deserializeHelper(const std::vector<std::string> &nodes,
                              int &index) {
    if (index >= nodes.size() || nodes[index] == "null") {
      ++index;
      return nullptr;
    }
    TreeNode *node = new TreeNode(std::stoi(nodes[index++]));
    node->left = deserializeHelper(nodes, index);
    node->right = deserializeHelper(nodes, index);
    return node;
  }

  std::vector<std::string> split(const std::string &s, char delimiter) {
    std::vector<std::string> tokens;
    std::string token;
    std::istringstream tokenStream(s);
    while (std::getline(tokenStream, token, delimiter)) {
      tokens.push_back(token);
    }
    return tokens;
  }
};

package main

import (
	"strconv"
	"strings"
)

type Codec struct{}

func NewCodeC() (_ Codec) {
	return
}

func (Codec) serialize(root *TreeNode) string {
	sb := &strings.Builder{}
	var dfs func(*TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			sb.WriteString("null,")
			return
		}
		sb.WriteString(strconv.Itoa(node.Val))
		sb.WriteByte(',')
		dfs(node.Left)
		dfs(node.Right)
	}
	dfs(root)
	return sb.String()
}

func (Codec) deserialize(data string) *TreeNode {
	sp := strings.Split(data, ",")
	var build func() *TreeNode
	build = func() *TreeNode {
		if sp[0] == "null" {
			sp = sp[1:]
			return nil
		}
		val, _ := strconv.Atoi(sp[0])
		sp = sp[1:]
		return &TreeNode{val, build(), build()}
	}
	return build()
}

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  int sumNumbers(TreeNode *root) { return dfs(root, 0); }

private:
  int dfs(TreeNode *node, int prevSum) {
    if (!node) {
      return 0;
    }
    int sum = prevSum * 10 + node->val;
    if (!node->left && !node->right) {
      return sum;
    }
    return dfs(node->left, sum) + dfs(node->right, sum);
  }
};

package main

func dfs(root *TreeNode, prevSum int) int {
	if root == nil {
		return 0
	}
	sum := prevSum*10 + root.Val
	if root.Left == nil && root.Right == nil {
		return sum
	}
	return dfs(root.Left, sum) + dfs(root.Right, sum)
}

func sumNumbers(root *TreeNode) int {
	return dfs(root, 0)
}

#include <unordered_map>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  int pathSum(TreeNode *root, int targetSum) {
    std::unordered_map<long long, int> preSum;
    preSum[0] = 1;
    return dfs(root, 0, targetSum, preSum);
  }

private:
  int dfs(TreeNode *node, long long curr, int targetSum,
          std::unordered_map<long long, int> &preSum) {
    if (!node) {
      return 0;
    }
    curr += node->val;
    int ans = preSum[curr - targetSum];
    preSum[curr]++;
    ans += dfs(node->left, curr, targetSum, preSum);
    ans += dfs(node->right, curr, targetSum, preSum);
    preSum[curr]--;
    return ans;
  }
};

package main

func pathSum(root *TreeNode, targetSum int) (ans int) {
	preSum := map[int64]int{0: 1}
	var dfs func(*TreeNode, int64)
	dfs = func(node *TreeNode, curr int64) {
		if node == nil {
			return
		}
		curr += int64(node.Val)
		ans += preSum[curr-int64(targetSum)]
		preSum[curr]++
		dfs(node.Left, curr)
		dfs(node.Right, curr)
		preSum[curr]--
		return
	}
	dfs(root, 0)
	return
}

#include <algorithm>
#include <climits>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  int maxPathSum(TreeNode *root) {
    maxSum = INT_MIN;
    maxGain(root);
    return maxSum;
  }

private:
  int maxSum;

  int maxGain(TreeNode *node) {
    if (!node) {
      return 0;
    }

    // Recursively calculate the maximum contribution of the left and right
    // subtrees Only consider positive contributions
    int leftGain = std::max(maxGain(node->left), 0);
    int rightGain = std::max(maxGain(node->right), 0);

    // The price to start a new path where `node` is the highest node
    int priceNewPath = node->val + leftGain + rightGain;

    // Update the maximum sum if the new path is better
    maxSum = std::max(maxSum, priceNewPath);

    // Return the maximum gain if continuing the same path
    return node->val + std::max(leftGain, rightGain);
  }
};

package main

import "math"

func maxPathSum(root *TreeNode) int {
	maxSum := math.MinInt32
	var maxGain func(*TreeNode) int
	maxGain = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		// 递归计算左右子节点的最大贡献值
		// 只有在最大贡献值大于 0 时，才会选取对应子节点
		leftGain := max(maxGain(node.Left), 0)
		rightGain := max(maxGain(node.Right), 0)

		// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
		priceNewPath := node.Val + leftGain + rightGain

		// 更新答案
		maxSum = max(maxSum, priceNewPath)

		// 返回节点的最大贡献值
		return node.Val + max(leftGain, rightGain)
	}
	maxGain(root)
	return maxSum
}

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  TreeNode *increasingBST(TreeNode *root) {
    TreeNode *dummyNode = new TreeNode(0);
    TreeNode *resNode = dummyNode;

    inorder(root, resNode);

    return dummyNode->right;
  }

private:
  void inorder(TreeNode *node, TreeNode *&resNode) {
    if (!node) {
      return;
    }
    inorder(node->left, resNode);

    // Modify the node pointers during in-order traversal
    resNode->right = node;
    node->left = nullptr;
    resNode = node;

    inorder(node->right, resNode);
  }
};

package main

func increasingBST(root *TreeNode) *TreeNode {
	dummyNode := &TreeNode{}
	resNode := dummyNode

	var inorder func(*TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)

		// 在中序遍历的过程中修改节点指向
		resNode.Right = node
		node.Left = nil
		resNode = node

		inorder(node.Right)
	}
	inorder(root)

	return dummyNode.Right
}

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  TreeNode *inorderSuccessor(TreeNode *root, TreeNode *p) {
    TreeNode *successor = nullptr;
    if (p->right) {
      successor = p->right;
      while (successor->left) {
        successor = successor->left;
      }
      return successor;
    }
    TreeNode *node = root;
    while (node) {
      if (node->val > p->val) {
        successor = node;
        node = node->left;
      } else {
        node = node->right;
      }
    }
    return successor;
  }
};

package main

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	var successor *TreeNode
	if p.Right != nil {
		successor = p.Right
		for successor.Left != nil {
			successor = successor.Left
		}
		return successor
	}
	node := root
	for node != nil {
		if node.Val > p.Val {
			successor = node
			node = node.Left
		} else {
			node = node.Right
		}
	}
	return successor
}

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  TreeNode *convertBST(TreeNode *root) {
    int sum = 0;
    dfs(root, sum);
    return root;
  }

private:
  void dfs(TreeNode *node, int &sum) {
    if (node != nullptr) {
      dfs(node->right, sum);
      sum += node->val;
      node->val = sum;
      dfs(node->left, sum);
    }
  }
};

package main

func convertBST(root *TreeNode) *TreeNode {
	sum := 0
	var dfs func(*TreeNode)
	dfs = func(node *TreeNode) {
		if node != nil {
			dfs(node.Right)
			sum += node.Val
			node.Val = sum
			dfs(node.Left)
		}
	}
	dfs(root)
	return root
}

#include <stack>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
public:
  BSTIterator(TreeNode *root) : cur(root) {}

  int next() {
    while (cur) {
      stack.push(cur);
      cur = cur->left;
    }
    cur = stack.top();
    stack.pop();
    int val = cur->val;
    cur = cur->right;
    return val;
  }

  bool hasNext() { return cur != nullptr || !stack.empty(); }

private:
  std::stack<TreeNode *> stack;
  TreeNode *cur;
};

package main

type BSTIterator struct {
	stack []*TreeNode
	cur   *TreeNode
}

func NewBSTIterator(root *TreeNode) BSTIterator {
	return BSTIterator{cur: root}
}

func (it *BSTIterator) Next() int {
	for node := it.cur; node != nil; node = node.Left {
		it.stack = append(it.stack, node)
	}
	it.cur, it.stack = it.stack[len(it.stack)-1], it.stack[:len(it.stack)-1]
	val := it.cur.Val
	it.cur = it.cur.Right
	return val
}

func (it *BSTIterator) HasNext() bool {
	return it.cur != nil || len(it.stack) > 0
}

#include <unordered_set>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
  bool findTarget(TreeNode *root, int k) {
    std::unordered_set<int> visit;
    bool flag = false;
    inorder(root, k, visit, flag);
    return flag;
  }

private:
  void inorder(TreeNode *node, int k, std::unordered_set<int> &visit,
               bool &flag) {
    if (!node || flag) {
      return;
    }
    inorder(node->left, k, visit, flag);
    if (visit.count(k - node->val)) {
      flag = true;
      return;
    }
    visit.insert(node->val);
    inorder(node->right, k, visit, flag);
  }
};

package main

func findTarget(root *TreeNode, k int) bool {
	visit := map[int]struct{}{}
	flag := false
	var inorder func(*TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil || flag {
			return
		}
		inorder(node.Left)
		if _, ok := visit[k-node.Val]; ok {
			flag = true
			return
		}
		visit[node.Val] = struct{}{}
		inorder(node.Right)
	}
	inorder(root)
	return flag
}

#include <cmath>
#include <unordered_map>
#include <vector>

int getID(int x, int w) {
  if (x >= 0) {
    return x / w;
  }
  return (x + 1) / w - 1;
}

bool containsNearbyAlmostDuplicate(const std::vector<int> &nums, int k, int t) {
  std::unordered_map<int, int> mp;
  for (int i = 0; i < nums.size(); ++i) {
    int x = nums[i];
    int id = getID(x, t + 1);
    if (mp.count(id)) {
      return true;
    }
    if (mp.count(id - 1) && std::abs(x - mp[id - 1]) <= t) {
      return true;
    }
    if (mp.count(id + 1) && std::abs(x - mp[id + 1]) <= t) {
      return true;
    }
    mp[id] = x;
    if (i >= k) {
      mp.erase(getID(nums[i - k], t + 1));
    }
  }
  return false;
}

int abs(int x) { return x < 0 ? -x : x; }

package main

func getID(x, w int) int {
	if x >= 0 {
		return x / w
	}
	return (x+1)/w - 1
}

func containsNearbyAlmostDuplicate(nums []int, k, t int) bool {
	mp := map[int]int{}
	for i, x := range nums {
		id := getID(x, t+1)
		if _, has := mp[id]; has {
			return true
		}
		if y, has := mp[id-1]; has && abs(x-y) <= t {
			return true
		}
		if y, has := mp[id+1]; has && abs(x-y) <= t {
			return true
		}
		mp[id] = x
		if i >= k {
			delete(mp, getID(nums[i-k], t+1))
		}
	}
	return false
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

#include <map>

class MyCalendar {
public:
  MyCalendar() {}

  bool book(int start, int end) {
    if (query(start, end - 1, 0, 1e9, 1)) {
      return false;
    }
    update(start, end - 1, 0, 1e9, 1);
    return true;
  }

private:
  std::map<int, bool> tree, lazy;

  bool query(int start, int end, int l, int r, int idx) {
    if (r < start || end < l) {
      return false;
    }
    if (lazy[idx]) { // If the interval is already booked, return true
      return true;
    }
    if (start <= l && r <= end) {
      return tree[idx];
    }
    int mid = (l + r) >> 1;
    return query(start, end, l, mid, 2 * idx) ||
           query(start, end, mid + 1, r, 2 * idx + 1);
  }

  void update(int start, int end, int l, int r, int idx) {
    if (r < start || end < l) {
      return;
    }
    if (start <= l && r <= end) {
      tree[idx] = true;
      lazy[idx] = true;
    } else {
      int mid = (l + r) >> 1;
      update(start, end, l, mid, 2 * idx);
      update(start, end, mid + 1, r, 2 * idx + 1);
      tree[idx] = true;
      if (lazy[2 * idx] && lazy[2 * idx + 1]) {
        lazy[idx] = true;
      }
    }
  }
};

package main

type MyCalendar struct {
	tree, lazy map[int]bool
}

func NewMyCalendar() MyCalendar {
	return MyCalendar{map[int]bool{}, map[int]bool{}}
}

func (c MyCalendar) query(start, end, l, r, idx int) bool {
	if r < start || end < l {
		return false
	}
	if c.lazy[idx] { // 如果该区间已被预订，则直接返回
		return true
	}
	if start <= l && r <= end {
		return c.tree[idx]
	}
	mid := (l + r) >> 1
	return c.query(start, end, l, mid, 2*idx) ||
		c.query(start, end, mid+1, r, 2*idx+1)
}

func (c MyCalendar) update(start, end, l, r, idx int) {
	if r < start || end < l {
		return
	}
	if start <= l && r <= end {
		c.tree[idx] = true
		c.lazy[idx] = true
	} else {
		mid := (l + r) >> 1
		c.update(start, end, l, mid, 2*idx)
		c.update(start, end, mid+1, r, 2*idx+1)
		c.tree[idx] = true
		if c.lazy[2*idx] && c.lazy[2*idx+1] {
			c.lazy[idx] = true
		}
	}
}

func (c MyCalendar) Book(start, end int) bool {
	if c.query(start, end-1, 0, 1e9, 1) {
		return false
	}
	c.update(start, end-1, 0, 1e9, 1)
	return true
}

#include <functional>
#include <queue>
#include <vector>

class KthLargest {
public:
  KthLargest(int k, std::vector<int> &nums) : k(k) {
    for (int val : nums) {
      add(val);
    }
  }

  int add(int val) {
    if (minHeap.size() < k) {
      minHeap.push(val);
    } else if (val > minHeap.top()) {
      minHeap.push(val);
      if (minHeap.size() > k) {
        minHeap.pop();
      }
    }
    return minHeap.top();
  }

private:
  int k;
  std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
};

package main

import (
	"container/heap"
	"sort"
)

type KthLargest struct {
	sort.IntSlice
	k int
}

func NewKthLargest(k int, nums []int) KthLargest {
	kl := KthLargest{k: k}
	for _, val := range nums {
		kl.Add(val)
	}
	return kl
}

func (kl *KthLargest) Push(v interface{}) {
	kl.IntSlice = append(kl.IntSlice, v.(int))
}

func (kl *KthLargest) Pop() interface{} {
	a := kl.IntSlice
	v := a[len(a)-1]
	kl.IntSlice = a[:len(a)-1]
	return v
}

func (kl *KthLargest) Add(val int) int {
	heap.Push(kl, val)
	if kl.Len() > kl.k {
		heap.Pop(kl)
	}
	return kl.IntSlice[0]
}

#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>

class IHeap {
public:
  bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    return a.second > b.second;
  }
};

std::vector<int> topKFrequent(std::vector<int> &nums, int k) {
  std::unordered_map<int, int> occurrences;
  for (int num : nums) {
    occurrences[num]++;
  }

  std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                      IHeap>
      h;
  for (const auto &[key, value] : occurrences) {
    h.emplace(key, value);
    if (h.size() > k) {
      h.pop();
    }
  }

  std::vector<int> ret(k);
  for (int i = k - 1; i >= 0; --i) {
    ret[i] = h.top().first;
    h.pop();
  }

  return ret;
}

package main

import "container/heap"

func topKFrequent(nums []int, k int) []int {
	occurrences := map[int]int{}
	for _, num := range nums {
		occurrences[num]++
	}
	h := &IHeap{}
	heap.Init(h)
	for key, value := range occurrences {
		heap.Push(h, [2]int{key, value})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	ret := make([]int, k)
	for i := 0; i < k; i++ {
		ret[k-i-1] = heap.Pop(h).([2]int)[0]
	}
	return ret
}

type IHeap [][2]int

func (h IHeap) Len() int           { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}

func (h *IHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

#include <queue>
#include <tuple>
#include <vector>

using namespace std;

vector<vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2,
                                   int k) {
  vector<vector<int>> ans;
  auto comp = [](const pair<int, int> &a, const pair<int, int> &b) {
    return a.first + a.second > b.first + b.second;
  };

  priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)>
      minHeap(comp);

  int m = nums1.size(), n = nums2.size();
  for (int i = 0; i < k && i < m; ++i) {
    minHeap.emplace(i, 0);
  }

  while (!minHeap.empty() && ans.size() < k) {
    auto [i, j] = minHeap.top();
    minHeap.pop();
    ans.push_back({nums1[i], nums2[j]});
    if (j + 1 < n) {
      minHeap.emplace(i, j + 1);
    }
  }

  return ans;
}

package main

import "container/heap"

func kSmallestPairs(nums1, nums2 []int, k int) (ans [][]int) {
	h := hp{nums1: nums1, nums2: nums2}
	m, n := len(nums1), len(nums2)
	for i := 0; i < k && i < m; i++ {
		heap.Push(&h, pair{i, 0})
	}
	for h.Len() > 0 && len(ans) < k {
		p := heap.Pop(&h).(pair)
		i, j := p.i, p.j
		ans = append(ans, []int{nums1[i], nums2[j]})
		if j+1 < n {
			heap.Push(&h, pair{i, j + 1})
		}
	}
	return
}

type hp struct {
	data         []pair
	nums1, nums2 []int
}

type pair struct {
	i, j int
}

func (h hp) Len() int {
	return len(h.data)
}

func (h hp) Less(i, j int) bool {
	p1, p2 := h.data[i], h.data[j]
	return h.nums1[p1.i]+h.nums2[p1.j] < h.nums1[p2.i]+h.nums2[p2.j]
}

func (h hp) Swap(i, j int) {
	h.data[i], h.data[j] = h.data[j], h.data[i]
}

func (h *hp) Push(val interface{}) {
	h.data = append(h.data, val.(pair))
}

func (h *hp) Pop() interface{} {
	data := h.data
	val := data[len(data)-1]
	h.data = data[:len(data)-1]
	return val
}

#include <string>
#include <vector>

class Trie {
public:
  Trie() : children(26, nullptr), isEnd(false) {}

  void Insert(const std::string &word) {
    Trie *node = this;
    for (char ch : word) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        node->children[ch] = new Trie();
      }
      node = node->children[ch];
    }
    node->isEnd = true;
  }

  bool Search(const std::string &word) {
    Trie *node = SearchPrefix(word);
    return node != nullptr && node->isEnd;
  }

  bool StartsWith(const std::string &prefix) {
    return SearchPrefix(prefix) != nullptr;
  }

private:
  std::vector<Trie *> children;
  bool isEnd;

  Trie *SearchPrefix(const std::string &prefix) {
    Trie *node = this;
    for (char ch : prefix) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        return nullptr;
      }
      node = node->children[ch];
    }
    return node;
  }
};

package main

type Trie struct {
	children [26]*Trie
	isEnd    bool
}

func Constructor() Trie {
	return Trie{}
}

func (t *Trie) Insert(word string) {
	node := t
	for _, ch := range word {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &Trie{}
		}
		node = node.children[ch]
	}
	node.isEnd = true
}

func (t *Trie) SearchPrefix(prefix string) *Trie {
	node := t
	for _, ch := range prefix {
		ch -= 'a'
		if node.children[ch] == nil {
			return nil
		}
		node = node.children[ch]
	}
	return node
}

func (t *Trie) Search(word string) bool {
	node := t.SearchPrefix(word)
	return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
	return t.SearchPrefix(prefix) != nil
}

#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Trie {
public:
  unordered_map<char, Trie *> children;
  bool isEnd = false;

  void insert(const string &word) {
    Trie *node = this;
    for (char c : word) {
      if (node->children.find(c) == node->children.end()) {
        node->children[c] = new Trie();
      }
      node = node->children[c];
    }
    node->isEnd = true;
  }

  string searchRoot(const string &word) {
    Trie *node = this;
    for (int i = 0; i < word.size(); ++i) {
      char c = word[i];
      if (node->isEnd) {
        return word.substr(0, i);
      }
      if (node->children.find(c) == node->children.end()) {
        break;
      }
      node = node->children[c];
    }
    return word;
  }
};

string replaceWords(vector<string> &dictionary, const string &sentence) {
  Trie root;
  for (const string &word : dictionary) {
    root.insert(word);
  }

  istringstream iss(sentence);
  string word;
  string result;
  while (iss >> word) {
    if (!result.empty()) {
      result += " ";
    }
    result += root.searchRoot(word);
  }

  return result;
}

package main

import "strings"

func replaceWords(dictionary []string, sentence string) string {
	type trie map[rune]trie
	root := trie{}
	for _, s := range dictionary {
		cur := root
		for _, c := range s {
			if cur[c] == nil {
				cur[c] = trie{}
			}
			cur = cur[c]
		}
		cur['#'] = trie{}
	}

	words := strings.Split(sentence, " ")
	for i, word := range words {
		cur := root
		for j, c := range word {
			if cur['#'] != nil {
				words[i] = word[:j]
				break
			}
			if cur[c] == nil {
				break
			}
			cur = cur[c]
		}
	}
	return strings.Join(words, " ")
}

#include <string>
#include <vector>

class Trie {
public:
  Trie *children[26] = {nullptr};
  bool isEnd = false;
};

class MagicDictionary {
public:
  MagicDictionary() { root = new Trie(); }

  void BuildDict(const std::vector<std::string> &dictionary) {
    for (const std::string &word : dictionary) {
      Trie *node = root;
      for (char ch : word) {
        int idx = ch - 'a';
        if (node->children[idx] == nullptr) {
          node->children[idx] = new Trie();
        }
        node = node->children[idx];
      }
      node->isEnd = true;
    }
  }

  bool Search(const std::string &searchWord) {
    return dfs(root, searchWord, 0, false);
  }

private:
  Trie *root;

  bool dfs(Trie *node, const std::string &word, int index, bool modified) {
    if (index == word.size()) {
      return modified && node->isEnd;
    }
    int c = word[index] - 'a';
    if (node->children[c] != nullptr &&
        dfs(node->children[c], word, index + 1, modified)) {
      return true;
    }
    if (!modified) {
      for (int i = 0; i < 26; ++i) {
        if (i != c && node->children[i] != nullptr &&
            dfs(node->children[i], word, index + 1, true)) {
          return true;
        }
      }
    }
    return false;
  }
};

package main

type MagicDictionary struct {
	trie *trie
}

type trie struct {
	children [26]*trie
	isEnd    bool
}

/** Initialize your data structure here. */
func NewMagicDictionary() MagicDictionary {
	return MagicDictionary{trie: &trie{}}
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
	for _, word := range dictionary {
		cur := this.trie
		for _, ch := range word {
			idx := ch - 'a'
			if cur.children[idx] == nil {
				cur.children[idx] = &trie{}
			}
			cur = cur.children[idx]
		}
		cur.isEnd = true
	}
}

func (this *MagicDictionary) Search(searchWord string) bool {
	var dfs func(node *trie, searchWord string, modified bool) bool
	dfs = func(node *trie, searchWord string, modified bool) bool {
		if searchWord == "" {
			return modified && node.isEnd
		}
		c := searchWord[0] - 'a'
		if node.children[c] != nil && dfs(node.children[c], searchWord[1:], modified) {
			return true
		}
		if !modified {
			for i, child := range node.children {
				if i != int(c) && child != nil && dfs(child, searchWord[1:], true) {
					return true
				}
			}
		}
		return false
	}
	return dfs(this.trie, searchWord, false)
}

#include <algorithm>
#include <functional>
#include <string>
#include <vector>

class Trie {
public:
  Trie *child[26] = {nullptr};
  int depth = 1;

  Trie() = default;

  void Insert(const std::string &word) {
    Trie *curr = this;
    int n = word.size();
    for (int i = n - 1; i >= 0; --i) {
      int c = word[i] - 'a';
      if (curr->child[c] == nullptr) {
        curr->child[c] = new Trie();
      }
      curr->child[c]->depth = curr->depth + 1;
      curr = curr->child[c];
    }
  }
};

int minimumLengthEncoding(std::vector<std::string> &words) {
  Trie *root = new Trie();
  for (const std::string &word : words) {
    root->Insert(word);
  }

  int res = 0;
  std::function<void(Trie *)> dfs = [&](Trie *node) -> void {
    bool hasChild = false;
    for (int i = 0; i < 26; ++i) {
      if (node->child[i] != nullptr) {
        hasChild = true;
        dfs(node->child[i]);
      }
    }
    if (!hasChild) {
      res += node->depth;
    }
  };
  dfs(root);
  return res;
}

package main

type WordEncodeTrie struct {
	child [26]*WordEncodeTrie
	depth int
}

func NewTrie() *WordEncodeTrie {
	return &WordEncodeTrie{
		child: [26]*WordEncodeTrie{},
		depth: 1,
	}
}

func (t *WordEncodeTrie) Insert(word string) {
	curr := t
	n := len(word)
	for i := n - 1; i >= 0; i-- {
		c := word[i] - 'a'
		if curr.child[c] == nil {
			curr.child[c] = NewTrie()
		}
		curr.child[c].depth = curr.depth + 1
		curr = curr.child[c]
	}
}

func minimumLengthEncoding(words []string) int {
	t := NewTrie()
	for _, w := range words {
		t.Insert(w)
	}
	var res int
	var dfs func(node *WordEncodeTrie)
	dfs = func(node *WordEncodeTrie) {
		var hasChild bool
		for i := 0; i < 26; i++ {
			if node.child[i] != nil {
				hasChild = true
				dfs(node.child[i])
			}
		}
		if !hasChild {
			res += node.depth
		}
	}
	dfs(t)
	return res
}

#include <string>
#include <unordered_map>
#include <vector>

class TrieNode {
public:
  TrieNode *children[26] = {nullptr};
  int val = 0;
};

class MapSum {
public:
  MapSum() { root = new TrieNode(); }

  void Insert(const std::string &key, int val) {
    int delta = val;
    if (cnt.find(key) != cnt.end()) {
      delta -= cnt[key];
    }
    cnt[key] = val;
    TrieNode *node = root;
    for (char ch : key) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        node->children[ch] = new TrieNode();
      }
      node = node->children[ch];
      node->val += delta;
    }
  }

  int Sum(const std::string &prefix) {
    TrieNode *node = root;
    for (char ch : prefix) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        return 0;
      }
      node = node->children[ch];
    }
    return node->val;
  }

private:
  TrieNode *root;
  std::unordered_map<std::string, int> cnt;
};

package main

type TrieNode struct {
	children [26]*TrieNode
	val      int
}

type MapSum struct {
	root *TrieNode
	cnt  map[string]int
}

func NewMapSum() MapSum {
	return MapSum{
		&TrieNode{},
		map[string]int{},
	}
}

func (m *MapSum) Insert(key string, val int) {
	delta := val
	if m.cnt[key] > 0 {
		delta -= m.cnt[key]
	}
	m.cnt[key] = val
	node := m.root
	for _, ch := range key {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &TrieNode{}
		}
		node = node.children[ch]
		node.val += delta
	}
}

func (m *MapSum) Sum(prefix string) int {
	node := m.root
	for _, ch := range prefix {
		ch -= 'a'
		if node.children[ch] == nil {
			return 0
		}
		node = node.children[ch]
	}
	return node.val
}

#include <algorithm>
#include <vector>

const int highBit = 30;

class Trie {
public:
  Trie *left = nullptr;
  Trie *right = nullptr;

  void add(int num) {
    Trie *cur = this;
    for (int i = highBit; i >= 0; --i) {
      int bit = (num >> i) & 1;
      if (bit == 0) {
        if (cur->left == nullptr) {
          cur->left = new Trie();
        }
        cur = cur->left;
      } else {
        if (cur->right == nullptr) {
          cur->right = new Trie();
        }
        cur = cur->right;
      }
    }
  }

  int check(int num) {
    Trie *cur = this;
    int x = 0;
    for (int i = highBit; i >= 0; --i) {
      int bit = (num >> i) & 1;
      if (bit == 0) {
        if (cur->right != nullptr) {
          cur = cur->right;
          x = x * 2 + 1;
        } else {
          cur = cur->left;
          x = x * 2;
        }
      } else {
        if (cur->left != nullptr) {
          cur = cur->left;
          x = x * 2 + 1;
        } else {
          cur = cur->right;
          x = x * 2;
        }
      }
    }
    return x;
  }
};

int findMaximumXOR(const std::vector<int> &nums) {
  Trie *root = new Trie();
  int x = 0;
  for (int i = 1; i < nums.size(); ++i) {
    root->add(nums[i - 1]);
    x = std::max(x, root->check(nums[i]));
  }
  return x;
}

package main

const highBit = 30

type xor_trie struct {
	left, right *xor_trie
}

func (t *xor_trie) add(num int) {
	cur := t
	for i := highBit; i >= 0; i-- {
		bit := num >> i & 1
		if bit == 0 {
			if cur.left == nil {
				cur.left = &xor_trie{}
			}
			cur = cur.left
		} else {
			if cur.right == nil {
				cur.right = &xor_trie{}
			}
			cur = cur.right
		}
	}
}

func (t *xor_trie) check(num int) (x int) {
	cur := t
	for i := highBit; i >= 0; i-- {
		bit := num >> i & 1
		if bit == 0 {
			// a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
			if cur.right != nil {
				cur = cur.right
				x = x*2 + 1
			} else {
				cur = cur.left
				x = x * 2
			}
		} else {
			// a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
			if cur.left != nil {
				cur = cur.left
				x = x*2 + 1
			} else {
				cur = cur.right
				x = x * 2
			}
		}
	}
	return
}

func findMaximumXOR(nums []int) (x int) {
	root := &xor_trie{}
	for i := 1; i < len(nums); i++ {
		// 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
		root.add(nums[i-1])
		// 将 nums[i] 看作 ai，找出最大的 x 更新答案
		x = max(x, root.check(nums[i]))
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

#include <vector>

int searchInsert(const std::vector<int> &nums, int target) {
  int n = nums.size();
  int left = 0, right = n - 1;
  int ans = n;
  while (left <= right) {
    int mid = (right - left) / 2 + left;
    if (target <= nums[mid]) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
}

package main

func searchInsert(nums []int, target int) int {
	n := len(nums)
	left, right := 0, n-1
	ans := n
	for left <= right {
		mid := (right-left)>>1 + left
		if target <= nums[mid] {
			ans = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return ans
}

#include <algorithm>
#include <vector>

int peakIndexInMountainArray(const std::vector<int> &arr) {
  return std::distance(arr.begin(), std::find_if(
                                        arr.begin(), arr.end() - 1,
                                        &{ return arr[i] > arr[i + 1]; }));
}

package main

import "sort"

func peakIndexInMountainArray(arr []int) int {
	return sort.Search(len(arr)-1, func(i int) bool { return arr[i] > arr[i+1] })
}

#include <vector>

int singleNonDuplicate(const std::vector<int> &nums) {
  int low = 0, high = nums.size() - 1;
  while (low < high) {
    int mid = low + (high - low) / 2;
    if (nums[mid] == nums[mid ^ 1]) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  return nums[low];
}

package main

func singleNonDuplicate(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		mid := low + (high-low)/2
		if nums[mid] == nums[mid^1] {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return nums[low]
}

#include <algorithm>
#include <cstdlib>
#include <vector>

class Solution {
public:
  Solution(std::vector<int> &w) {
    for (int i = 1; i < w.size(); ++i) {
      w[i] += w[i - 1];
    }
    pre = w;
  }

  int PickIndex() {
    int x = rand() % pre.back() + 1;
    return std::lower_bound(pre.begin(), pre.end(), x) - pre.begin();
  }

private:
  std::vector<int> pre;
};

package main

import (
	"math/rand"
	"sort"
)

type WeightRandom struct {
	pre []int
}

func NewWeightRandom(w []int) WeightRandom {
	for i := 1; i < len(w); i++ {
		w[i] += w[i-1]
	}
	return WeightRandom{w}
}

func (s *WeightRandom) PickIndex() int {
	x := rand.Intn(s.pre[len(s.pre)-1]) + 1
	return sort.SearchInts(s.pre, x)
}

int mySqrt(int x) {
  int l = 0, r = x;
  int ans = -1;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (mid * mid <= x) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return ans;
}

package main

func mySqrt(x int) int {
	l, r := 0, x
	ans := -1
	for l <= r {
		mid := l + (r-l)/2
		if mid*mid <= x {
			ans = mid
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return ans
}

#include <algorithm>
#include <vector>

int minEatingSpeed(const std::vector<int> &piles, int h) {
  int maxPile = *std::max_element(piles.begin(), piles.end());
  return 1 + std::lower_bound(1, maxPile - 1, [&](int speed) -> bool {
           int time = 0;
           for (int pile : piles) {
             time += (pile + speed - 1) / speed;
           }
           return time <= h;
         });
}

package main

import "sort"

func minEatingSpeed(piles []int, h int) int {
	max := 0
	for _, pile := range piles {
		if pile > max {
			max = pile
		}
	}
	return 1 + sort.Search(max-1, func(speed int) bool {
		speed++
		time := 0
		for _, pile := range piles {
			time += (pile + speed - 1) / speed
		}
		return time <= h
	})
}

#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> merge(vector<vector<int>> &intervals) {
  sort(intervals.begin(), intervals.end(),
       [](const vector<int> &a, const vector<int> &b) {
         return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
       });

  vector<vector<int>> res;
  for (const auto &interval : intervals) {
    if (res.empty() || res.back()[1] < interval[0]) {
      res.push_back(interval);
    } else {
      res.back()[1] = max(res.back()[1], interval[1]);
    }
  }
  return res;
}

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

package main

import "sort"

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0] || (intervals[i][0] == intervals[j][0] && intervals[i][1] < intervals[j][1])
	})
	var res [][]int
	for _, interval := range intervals {
		if len(res) == 0 || res[len(res)-1][1] < interval[0] {
			res = append(res, interval)
		} else {
			res[len(res)-1][1] = max(res[len(res)-1][1], interval[1])
		}
	}
	return res
}

#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

class ZSet {
public:
  void insert(int key) { data[key]++; }

  void erase(int key) { data.erase(key); }

  vector<int> keys() const {
    vector<int> res;
    for (const auto &[key, _] : data) {
      res.push_back(key);
    }
    sort(res.begin(), res.end());
    return res;
  }

  int count(int key) const {
    auto it = data.find(key);
    return it != data.end() ? it->second : 0;
  }

private:
  unordered_map<int, int> data;
};

vector<int> relativeSortArray(vector<int> &arr1, const vector<int> &arr2) {
  ZSet zs;
  for (int val : arr1) {
    zs.insert(val);
  }

  vector<int> res;
  for (int val : arr2) {
    int count = zs.count(val);
    res.insert(res.end(), count, val);
    zs.erase(val);
  }

  vector<int> remainingKeys = zs.keys();
  for (int key : remainingKeys) {
    int count = zs.count(key);
    res.insert(res.end(), count, key);
  }

  return res;
}

package main

import "sort"

type zset map[int]int

func (zs *zset) keys() []int {
	res := []int{}
	for key := range *zs {
		res = append(res, key)
	}
	sort.Ints(res)
	return res
}

func relativeSortArray(arr1 []int, arr2 []int) []int {
	zs := zset{}
	for _, val := range arr1 {
		zs[val]++
	}

	res := make([]int, 0, len(arr1))
	for _, val := range arr2 {
		for i := 0; i < zs[val]; i++ {
			res = append(res, val)
		}
		delete(zs, val)
	}
	for _, key := range zs.keys() {
		for i := 0; i < zs[key]; i++ {
			res = append(res, key)
		}
	}
	return res
}

#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;

int partition(vector<int> &a, int l, int r) {
  int x = a[r];
  int i = l - 1;
  for (int j = l; j < r; ++j) {
    if (a[j] <= x) {
      ++i;
      swap(a[i], a[j]);
    }
  }
  swap(a[i + 1], a[r]);
  return i + 1;
}

int randomPartition(vector<int> &a, int l, int r) {
  int i = rand() % (r - l + 1) + l;
  swap(a[i], a[r]);
  return partition(a, l, r);
}

int quickSelect(vector<int> &a, int l, int r, int index) {
  int q = randomPartition(a, l, r);
  if (q == index) {
    return a[q];
  } else if (q < index) {
    return quickSelect(a, q + 1, r, index);
  }
  return quickSelect(a, l, q - 1, index);
}

int findKthLargest(vector<int> &nums, int k) {
  srand(time(0));
  return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}

package main

import (
	"math/rand"
	"time"
)

func findKthLargest(nums []int, k int) int {
	rand.Seed(time.Now().UnixNano())
	return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(a []int, l, r, index int) int {
	q := randomPartition(a, l, r)
	if q == index {
		return a[q]
	} else if q < index {
		return quickSelect(a, q+1, r, index)
	}
	return quickSelect(a, l, q-1, index)
}

func randomPartition(a []int, l, r int) int {
	i := rand.Int()%(r-l+1) + l
	a[i], a[r] = a[r], a[i]
	return partition(a, l, r)
}

func partition(a []int, l, r int) int {
	x := a[r]
	i := l - 1
	for j := l; j < r; j++ {
		if a[j] <= x {
			i++
			a[i], a[j] = a[j], a[i]
		}
	}
	a[i+1], a[r] = a[r], a[i+1]
	return i + 1
}

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

ListNode *merge(ListNode *head1, ListNode *head2) {
  ListNode dummyHead(0);
  ListNode *temp = &dummyHead;
  ListNode *temp1 = head1;
  ListNode *temp2 = head2;

  while (temp1 != nullptr && temp2 != nullptr) {
    if (temp1->val <= temp2->val) {
      temp->next = temp1;
      temp1 = temp1->next;
    } else {
      temp->next = temp2;
      temp2 = temp2->next;
    }
    temp = temp->next;
  }

  if (temp1 != nullptr) {
    temp->next = temp1;
  } else if (temp2 != nullptr) {
    temp->next = temp2;
  }

  return dummyHead.next;
}

ListNode *sort(ListNode *head, ListNode *tail) {
  if (head == nullptr) {
    return head;
  }

  if (head->next == tail) {
    head->next = nullptr;
    return head;
  }

  ListNode *slow = head;
  ListNode *fast = head;
  while (fast != tail) {
    slow = slow->next;
    fast = fast->next;
    if (fast != tail) {
      fast = fast->next;
    }
  }

  ListNode *mid = slow;
  return merge(sort(head, mid), sort(mid, tail));
}

ListNode *sortList(ListNode *head) { return sort(head, nullptr); }

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func MergeList(head1, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	temp, temp1, temp2 := dummyHead, head1, head2
	for temp1 != nil && temp2 != nil {
		if temp1.Val <= temp2.Val {
			temp.Next = temp1
			temp1 = temp1.Next
		} else {
			temp.Next = temp2
			temp2 = temp2.Next
		}
		temp = temp.Next
	}
	if temp1 != nil {
		temp.Next = temp1
	} else if temp2 != nil {
		temp.Next = temp2
	}
	return dummyHead.Next
}

func SortList(head, tail *ListNode) *ListNode {
	if head == nil {
		return head
	}

	if head.Next == tail {
		head.Next = nil
		return head
	}

	slow, fast := head, head
	for fast != tail {
		slow = slow.Next
		fast = fast.Next
		if fast != tail {
			fast = fast.Next
		}
	}

	mid := slow
	return MergeList(SortList(head, mid), SortList(mid, tail))
}

func sortList(head *ListNode) *ListNode {
	return SortList(head, nil)
}

#include <queue>
#include <vector>

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
  ListNode dummyHead(0);
  ListNode *p = &dummyHead;
  ListNode *p1 = list1;
  ListNode *p2 = list2;

  while (p1 != nullptr && p2 != nullptr) {
    if (p1->val > p2->val) {
      p->next = p2;
      p2 = p2->next;
    } else {
      p->next = p1;
      p1 = p1->next;
    }
    p = p->next;
  }

  if (p1 != nullptr) {
    p->next = p1;
  }
  if (p2 != nullptr) {
    p->next = p2;
  }

  return dummyHead.next;
}

ListNode *mergeKLists(std::vector<ListNode *> &lists) {
  ListNode *res = nullptr;
  for (ListNode *list : lists) {
    res = mergeTwoLists(res, list);
  }
  return res;
}

package main

// 合并K个升序链表
func mergeKLists(lists []*ListNode) (res *ListNode) {
	for _, v := range lists {
		res = mergeTwoLists(res, v)
	}
	return res
}

// 合并两个升序链表
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	//初始化一个虚拟的头节点
	newList := &ListNode{}
	p := newList
	p1 := list1
	p2 := list2
	//遍历对比两个指针值的大小，有一个走完了就停止
	for p1 != nil && p2 != nil {
		//将值小的节点接到p指针后面
		if p1.Val > p2.Val {
			p.Next = p2
			p2 = p2.Next
		} else {
			p.Next = p1
			p1 = p1.Next
		}
		//p指针前进
		p = p.Next
	}
	//将未比较的剩余节点都放到p指针后面
	if p1 != nil {
		p.Next = p1
	}
	if p2 != nil {
		p.Next = p2
	}
	//返回虚拟头节点的下一个节点就是真正的头节点
	return newList.Next
}

#include <vector>

using namespace std;

vector<vector<int>> subsets(vector<int> &nums) {
  vector<vector<int>> ans;
  int n = nums.size();
  for (int mask = 0; mask < (1 << n); ++mask) {
    vector<int> set;
    for (int i = 0; i < n; ++i) {
      if (mask & (1 << i)) {
        set.push_back(nums[i]);
      }
    }
    ans.push_back(set);
  }
  return ans;
}

package main

func subsets(nums []int) (ans [][]int) {
	n := len(nums)
	for mask := 0; mask < 1<<n; mask++ {
		set := []int{}
		for i, v := range nums {
			if mask>>i&1 > 0 {
				set = append(set, v)
			}
		}
		ans = append(ans, append([]int(nil), set...))
	}
	return
}

#include <vector>

using namespace std;

void dfs(int cur, int n, int k, vector<int> &temp, vector<vector<int>> &ans) {
  // Pruning: if the remaining elements plus the current temp size is less than
  // k, return
  if (temp.size() + (n - cur + 1) < k) {
    return;
  }
  // Record valid answers
  if (temp.size() == k) {
    ans.push_back(temp);
    return;
  }
  // Consider the current position
  temp.push_back(cur);
  dfs(cur + 1, n, k, temp, ans);
  temp.pop_back();
  // Consider not choosing the current position
  dfs(cur + 1, n, k, temp, ans);
}

vector<vector<int>> combine(int n, int k) {
  vector<vector<int>> ans;
  vector<int> temp;
  dfs(1, n, k, temp, ans);
  return ans;
}

package main

func combine(n int, k int) (ans [][]int) {
	temp := []int{}
	var dfs func(int)
	dfs = func(cur int) {
		// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
		if len(temp)+(n-cur+1) < k {
			return
		}
		// 记录合法的答案
		if len(temp) == k {
			comb := make([]int, k)
			copy(comb, temp)
			ans = append(ans, comb)
			return
		}
		// 考虑选择当前位置
		temp = append(temp, cur)
		dfs(cur + 1)
		temp = temp[:len(temp)-1]
		// 考虑不选择当前位置
		dfs(cur + 1)
	}
	dfs(1)
	return
}

#include <vector>

using namespace std;

void dfs(const vector<int> &candidates, int target, int idx, vector<int> &comb,
         vector<vector<int>> &ans) {
  if (idx == candidates.size()) {
    return;
  }
  if (target == 0) {
    ans.push_back(comb);
    return;
  }
  // Skip the current number
  dfs(candidates, target, idx + 1, comb, ans);
  // Choose the current number
  if (target - candidates[idx] >= 0) {
    comb.push_back(candidates[idx]);
    dfs(candidates, target - candidates[idx], idx, comb, ans);
    comb.pop_back();
  }
}

vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
  vector<vector<int>> ans;
  vector<int> comb;
  dfs(candidates, target, 0, comb, ans);
  return ans;
}

package main

func combinationSum(candidates []int, target int) (ans [][]int) {
	comb := []int{}
	var dfs func(target, idx int)
	dfs = func(target, idx int) {
		if idx == len(candidates) {
			return
		}
		if target == 0 {
			ans = append(ans, append([]int(nil), comb...))
			return
		}
		// 直接跳过
		dfs(target, idx+1)
		// 选择当前数
		if target-candidates[idx] >= 0 {
			comb = append(comb, candidates[idx])
			dfs(target-candidates[idx], idx)
			comb = comb[:len(comb)-1]
		}
	}
	dfs(target, 0)
	return
}

#include <algorithm>
#include <vector>

using namespace std;

void dfs(int pos, int rest, const vector<pair<int, int>> &freq,
         vector<int> &sequence, vector<vector<int>> &ans) {
  if (rest == 0) {
    ans.push_back(sequence);
    return;
  }
  if (pos == freq.size() || rest < freq[pos].first) {
    return;
  }

  dfs(pos + 1, rest, freq, sequence, ans);

  int most = min(rest / freq[pos].first, freq[pos].second);
  for (int i = 1; i <= most; ++i) {
    sequence.push_back(freq[pos].first);
    dfs(pos + 1, rest - i * freq[pos].first, freq, sequence, ans);
  }
  sequence.resize(sequence.size() - most);
}

vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
  sort(candidates.begin(), candidates.end());
  vector<pair<int, int>> freq;
  for (int num : candidates) {
    if (freq.empty() || num != freq.back().first) {
      freq.emplace_back(num, 1);
    } else {
      ++freq.back().second;
    }
  }

  vector<vector<int>> ans;
  vector<int> sequence;
  dfs(0, target, freq, sequence, ans);
  return ans;
}

int min(int a, int b) { return (a < b) ? a : b; }

package main

import "sort"

func combinationSum2(candidates []int, target int) (ans [][]int) {
	sort.Ints(candidates)
	var freq [][2]int // [值，次数]
	for _, num := range candidates {
		if freq == nil || num != freq[len(freq)-1][0] {
			freq = append(freq, [2]int{num, 1})
		} else {
			freq[len(freq)-1][1]++
		}
	}

	var sequence []int
	var dfs func(pos, rest int)
	dfs = func(pos, rest int) {
		if rest == 0 {
			ans = append(ans, append([]int(nil), sequence...))
			return
		}
		if pos == len(freq) || rest < freq[pos][0] {
			return
		}

		dfs(pos+1, rest)

		most := min(rest/freq[pos][0], freq[pos][1])
		for i := 1; i <= most; i++ {
			sequence = append(sequence, freq[pos][0])
			dfs(pos+1, rest-i*freq[pos][0])
		}
		sequence = sequence[:len(sequence)-most]
	}
	dfs(0, target)
	return
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

#include <vector>

using namespace std;

void dfs(vector<int> &nums, vector<bool> &vis, vector<int> &path,
         vector<vector<int>> &ans) {
  if (path.size() == nums.size()) {
    ans.push_back(path);
    return;
  }
  for (int i = 0; i < nums.size(); ++i) {
    if (!vis[i]) {
      vis[i] = true;
      path.push_back(nums[i]);
      dfs(nums, vis, path, ans);
      vis[i] = false;
      path.pop_back();
    }
  }
}

vector<vector<int>> permute(vector<int> &nums) {
  vector<vector<int>> ans;
  vector<int> path;
  vector<bool> vis(nums.size(), false);
  dfs(nums, vis, path, ans);
  return ans;
}

package main

func permute(nums []int) [][]int {
	n := len(nums)
	var ans [][]int
	var path []int
	vis := make([]bool, n)
	var dfs func()
	dfs = func() {
		if len(path) == n {
			ans = append(ans, append([]int{}, path...))
			return
		}
		for i := 0; i < n; i++ {
			if !vis[i] {
				vis[i] = true
				path = append(path, nums[i])
				dfs()
				vis[i] = false
				path = path[:len(path)-1]
			}
		}
	}
	dfs()
	return ans
}

#include <algorithm>
#include <vector>

using namespace std;

void backtrack(vector<int> &nums, vector<bool> &vis, vector<int> &perm,
               vector<vector<int>> &ans, int idx) {
  if (idx == nums.size()) {
    ans.push_back(perm);
    return;
  }
  for (int i = 0; i < nums.size(); ++i) {
    if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
      continue;
    }
    perm.push_back(nums[i]);
    vis[i] = true;
    backtrack(nums, vis, perm, ans, idx + 1);
    vis[i] = false;
    perm.pop_back();
  }
}

vector<vector<int>> permuteUnique(vector<int> &nums) {
  sort(nums.begin(), nums.end());
  vector<vector<int>> ans;
  vector<int> perm;
  vector<bool> vis(nums.size(), false);
  backtrack(nums, vis, perm, ans, 0);
  return ans;
}

package main

import "sort"

func permuteUnique(nums []int) (ans [][]int) {
	sort.Ints(nums)
	n := len(nums)
	perm := []int{}
	vis := make([]bool, n)
	var backtrack func(int)
	backtrack = func(idx int) {
		if idx == n {
			ans = append(ans, append([]int(nil), perm...))
			return
		}
		for i, v := range nums {
			if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
				continue
			}
			perm = append(perm, v)
			vis[i] = true
			backtrack(idx + 1)
			vis[i] = false
			perm = perm[:len(perm)-1]
		}
	}
	backtrack(0)
	return
}

#include <string>
#include <vector>

using namespace std;

vector<string> generateParenthesis(int n) {
  vector<vector<string>> dp(n + 1);
  dp[0] = {""};
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < i; ++j) {
      for (const string &left : dp[j]) {
        for (const string &right : dp[i - j - 1]) {
          dp[i].push_back("(" + left + ")" + right);
        }
      }
    }
  }
  return dp[n];
}

void dfs(int n, int leftCnt, int rightCnt, string &tmp, vector<string> &res) {
  if (tmp.size() == n * 2) {
    res.push_back(tmp);
    return;
  }
  if (leftCnt < n) {
    tmp.push_back('(');
    dfs(n, leftCnt + 1, rightCnt, tmp, res);
    tmp.pop_back();
  }
  if (leftCnt > rightCnt) {
    tmp.push_back(')');
    dfs(n, leftCnt, rightCnt + 1, tmp, res);
    tmp.pop_back();
  }
}

vector<string> generateParenthesisDFS(int n) {
  vector<string> res;
  string tmp;
  dfs(n, 0, 0, tmp, res);
  return res;
}

package main

// 动态规划版本
func generateParenthesisDP(n int) []string {
	dp := make([][]string, n+1)
	dp[0] = []string{""}
	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			for _, left := range dp[j] {
				for _, right := range dp[i-j-1] {
					dp[i] = append(dp[i], "("+left+")"+right)
				}
			}

		}
	}
	return dp[n]
}

// 递归版本
func generateParenthesisDFS(n int) []string {
	var res []string
	var leftCnt, rightCnt int
	var tmp []byte
	var dfs func(cnt int)
	dfs = func(cnt int) {
		if cnt == n*2 {
			res = append(res, string(tmp))
			return
		}
		if leftCnt < n {
			leftCnt++
			tmp = append(tmp, '(')
			dfs(cnt + 1)
			leftCnt--
			tmp = tmp[:len(tmp)-1]
		}
		if leftCnt > rightCnt {
			rightCnt++
			tmp = append(tmp, ')')
			dfs(cnt + 1)
			rightCnt--
			tmp = tmp[:len(tmp)-1]
		}
	}
	dfs(0)
	return res
}

#include <functional>
#include <string>
#include <vector>

using namespace std;

vector<vector<string>> partition(string s) {
  int n = s.size();
  vector<vector<bool>> f(n, vector<bool>(n, true));
  for (int i = n - 1; i >= 0; --i) {
    for (int j = i + 1; j < n; ++j) {
      f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
    }
  }

  vector<vector<string>> ans;
  vector<string> splits;
  function<void(int)> dfs = [&](int i) {
    if (i == n) {
      ans.push_back(splits);
      return;
    }
    for (int j = i; j < n; ++j) {
      if (f[i][j]) {
        splits.push_back(s.substr(i, j - i + 1));
        dfs(j + 1);
        splits.pop_back();
      }
    };
  };
  dfs(0);
  return ans;
}

package main

func palindrome_partition(s string) (ans [][]string) {
	n := len(s)
	f := make([][]bool, n)
	for i := range f {
		f[i] = make([]bool, n)
		for j := range f[i] {
			f[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = s[i] == s[j] && f[i+1][j-1]
		}
	}

	splits := []string{}
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			ans = append(ans, append([]string(nil), splits...))
			return
		}
		for j := i; j < n; j++ {
			if f[i][j] {
				splits = append(splits, s[i:j+1])
				dfs(j + 1)
				splits = splits[:len(splits)-1]
			}
		}
	}
	dfs(0)
	return
}

#include <string>
#include <vector>

using namespace std;

const int SEG_COUNT = 4;

vector<string> ans;
vector<int> segments(SEG_COUNT);

void dfs(const string &s, int segId, int segStart) {
  // If we have found 4 segments and traversed the entire string, it's a valid
  // IP address
  if (segId == SEG_COUNT) {
    if (segStart == s.size()) {
      string ipAddr;
      for (int i = 0; i < SEG_COUNT; ++i) {
        ipAddr += to_string(segments[i]);
        if (i != SEG_COUNT - 1) {
          ipAddr += ".";
        }
      }
      ans.push_back(ipAddr);
    }
    return;
  }

  // If we haven't found 4 segments but traversed the entire string, backtrack
  if (segStart == s.size()) {
    return;
  }

  // If the current number is 0, this segment can only be 0
  if (s[segStart] == '0') {
    segments[segId] = 0;
    dfs(s, segId + 1, segStart + 1);
    return;
  }

  // General case: enumerate each possibility and recurse
  int addr = 0;
  for (int segEnd = segStart; segEnd < s.size(); ++segEnd) {
    addr = addr * 10 + (s[segEnd] - '0');
    if (addr > 0 && addr <= 255) {
      segments[segId] = addr;
      dfs(s, segId + 1, segEnd + 1);
    } else {
      break;
    }
  }
}

vector<string> restoreIpAddresses(string s) {
  ans.clear();
  segments = vector<int>(SEG_COUNT);
  dfs(s, 0, 0);
  return ans;
}

package main

import "strconv"

const SEG_COUNT = 4

var (
	ans      []string
	segments []int
)

func restoreIpAddresses(s string) []string {
	segments = make([]int, SEG_COUNT)
	ans = []string{}
	dfs(s, 0, 0)
	return ans
}

func dfs(s string, segId, segStart int) {
	// 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
	if segId == SEG_COUNT {
		if segStart == len(s) {
			ipAddr := ""
			for i := 0; i < SEG_COUNT; i++ {
				ipAddr += strconv.Itoa(segments[i])
				if i != SEG_COUNT-1 {
					ipAddr += "."
				}
			}
			ans = append(ans, ipAddr)
		}
		return
	}

	// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
	if segStart == len(s) {
		return
	}
	// 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
	if s[segStart] == '0' {
		segments[segId] = 0
		dfs(s, segId+1, segStart+1)
	}
	// 一般情况，枚举每一种可能性并递归
	addr := 0
	for segEnd := segStart; segEnd < len(s); segEnd++ {
		addr = addr*10 + int(s[segEnd]-'0')
		if addr > 0 && addr <= 0xFF {
			segments[segId] = addr
			dfs(s, segId+1, segEnd+1)
		} else {
			break
		}
	}
}

#include <algorithm>
#include <vector>

using namespace std;

int minCostClimbingStairs(vector<int> &cost) {
  int n = cost.size();
  int pre = 0, cur = 0;
  for (int i = 2; i <= n; ++i) {
    int newCur = min(cur + cost[i - 1], pre + cost[i - 2]);
    pre = cur;
    cur = newCur;
  }
  return cur;
}

package main

func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	pre, cur := 0, 0
	for i := 2; i <= n; i++ {
		pre, cur = cur, min(cur+cost[i-1], pre+cost[i-2])
	}
	return cur
}

#include <algorithm>
#include <vector>

using namespace std;

int rob(vector<int> &nums) {
  if (nums.empty()) {
    return 0;
  }
  if (nums.size() == 1) {
    return nums[0];
  }
  vector<int> dp(nums.size());
  dp[0] = nums[0];
  dp[1] = max(nums[0], nums[1]);
  for (int i = 2; i < nums.size(); ++i) {
    dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  return dp.back();
}

int max(int x, int y) { return (x > y) ? x : y; }

package main

func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-2]+nums[i], dp[i-1])
	}
	return dp[len(nums)-1]
}

#include <algorithm>
#include <vector>

using namespace std;

int _rob(const vector<int> &nums) {
  int first = nums[0], second = max(nums[0], nums[1]);
  for (int i = 2; i < nums.size(); ++i) {
    int v = nums[i];
    int newSecond = max(first + v, second);
    first = second;
    second = newSecond;
  }
  return second;
}

int rob(vector<int> &nums) {
  int n = nums.size();
  if (n == 1) {
    return nums[0];
  }
  if (n == 2) {
    return max(nums[0], nums[1]);
  }
  vector<int> nums1(nums.begin(), nums.end() - 1);
  vector<int> nums2(nums.begin() + 1, nums.end());
  return max(_rob(nums1), _rob(nums2));
}

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

package main

func _rob(nums []int) int {
	first, second := nums[0], max(nums[0], nums[1])
	for _, v := range nums[2:] {
		first, second = second, max(first+v, second)
	}
	return second
}

func robCircle(nums []int) int {
	n := len(nums)
	if n == 1 {
		return nums[0]
	}
	if n == 2 {
		return max(nums[0], nums[1])
	}
	return max(_rob(nums[:n-1]), _rob(nums[1:]))
}

#include <algorithm>
#include <iostream>
#include <vector>

int minCost(std::vector<std::vector<int>> &costs) {
  std::vector<int> dp = costs[0];
  for (size_t i = 1; i < costs.size(); ++i) {
    std::vector<int> dpNew(3);
    for (int j = 0; j < 3; ++j) {
      dpNew[j] = std::min(dp[(j + 1) % 3], dp[(j + 2) % 3]) + costs[i][j];
    }
    dp = dpNew;
  }
  return std::min({dp[0], dp[1], dp[2]});
}

int main() {
  std::vector<std::vector<int>> costs = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
  std::cout << "Minimum cost: " << minCost(costs) << std::endl;
  return 0;
}

package main

func minCost(costs [][]int) int {
	dp := costs[0]
	for _, cost := range costs[1:] {
		dpNew := make([]int, 3)
		for j, c := range cost {
			dpNew[j] = min(dp[(j+1)%3], dp[(j+2)%3]) + c
		}
		dp = dpNew
	}
	return min(min(dp[0], dp[1]), dp[2])
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

#include <algorithm>
#include <iostream>
#include <string>

int min(int a, int b) { return (a < b) ? a : b; }

int minFlipsMonoIncr(const std::string &s) {
  int dp0 = 0, dp1 = 0;
  for (char c : s) {
    int dp0New = dp0, dp1New = std::min(dp0, dp1);
    if (c == '1') {
      dp0New++;
    } else {
      dp1New++;
    }
    dp0 = dp0New;
    dp1 = dp1New;
  }
  return std::min(dp0, dp1);
}

int main() {
  std::string s = "00110";
  std::cout << "Minimum flips: " << minFlipsMonoIncr(s) << std::endl;
  return 0;
}

package main

func minFlipsMonoIncr(s string) int {
	dp0, dp1 := 0, 0
	for _, c := range s {
		dp0New, dp1New := dp0, min(dp0, dp1)
		if c == '1' {
			dp0New++
		} else {
			dp1New++
		}
		dp0, dp1 = dp0New, dp1New
	}
	return min(dp0, dp1)
}

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

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

int lenLongestFibSubseq(const std::vector<int> &arr) {
  int n = arr.size();
  std::unordered_map<int, int> indices;
  for (int i = 0; i < n; ++i) {
    indices[arr[i]] = i;
  }
  std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = n - 1; j >= 0 && arr[j] * 2 > arr[i]; --j) {
      auto it = indices.find(arr[i] - arr[j]);
      if (it != indices.end()) {
        int k = it->second;
        dp[j][i] = max(dp[k][j] + 1, 3);
        ans = max(ans, dp[j][i]);
      }
    }
  }
  return ans;
}

int main() {
  std::vector<int> arr = {1, 3, 7, 11, 12, 14, 18};
  std::cout << "Length of longest Fibonacci-like subsequence: "
            << lenLongestFibSubseq(arr) << std::endl;
  return 0;
}

package main

func lenLongestFibSubseq(arr []int) (ans int) {
	n := len(arr)
	indices := make(map[int]int, n)
	for i, x := range arr {
		indices[x] = i
	}
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i, x := range arr {
		for j := n - 1; j >= 0 && arr[j]*2 > x; j-- {
			if k, ok := indices[x-arr[j]]; ok {
				dp[j][i] = max(dp[k][j]+1, 3)
				ans = max(ans, dp[j][i])
			}
		}
	}
	return
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <vector>

int minCut(const std::string &s) {
  int n = s.size();
  std::vector<std::vector<bool>> g(n, std::vector<bool>(n, true));
  for (int i = n - 1; i >= 0; --i) {
    for (int j = i + 1; j < n; ++j) {
      g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
    }
  }

  std::vector<int> f(n, INT_MAX);
  for (int i = 0; i < n; ++i) {
    if (g[0][i]) {
      f[i] = 0;
    } else {
      for (int j = 0; j < i; ++j) {
        if (g[j + 1][i]) {
          f[i] = std::min(f[i], f[j] + 1);
        }
      }
    }
  }
  return f[n - 1];
}

int main() {
  std::string s = "aab";
  std::cout << "Minimum cuts needed for a palindrome partitioning: "
            << minCut(s) << std::endl;
  return 0;
}

package main

import "math"

func minCut(s string) int {
	n := len(s)
	g := make([][]bool, n)
	for i := range g {
		g[i] = make([]bool, n)
		for j := range g[i] {
			g[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			g[i][j] = s[i] == s[j] && g[i+1][j-1]
		}
	}

	f := make([]int, n)
	for i := range f {
		if g[0][i] {
			continue
		}
		f[i] = math.MaxInt64
		for j := 0; j < i; j++ {
			if g[j+1][i] && f[j]+1 < f[i] {
				f[i] = f[j] + 1
			}
		}
	}
	return f[n-1]
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

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

int longestCommonSubsequence(const std::string &text1,
                             const std::string &text2) {
  int m = text1.size(), n = text2.size();
  std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if (text1[i] == text2[j]) {
        dp[i + 1][j + 1] = dp[i][j] + 1;
      } else {
        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
      }
    }
  }
  return dp[m][n];
}

int main() {
  std::string text1 = "abcde";
  std::string text2 = "ace";
  std::cout << "Length of longest common subsequence: "
            << longestCommonSubsequence(text1, text2) << std::endl;
  return 0;
}

package main

func longestCommonSubsequence(text1, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i, c1 := range text1 {
		for j, c2 := range text2 {
			if c1 == c2 {
				dp[i+1][j+1] = dp[i][j] + 1
			} else {
				dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
			}
		}
	}
	return dp[m][n]
}

#include <iostream>
#include <string>
#include <vector>

bool isInterleave(const std::string &s1, const std::string &s2,
                  const std::string &s3) {
  int n = s1.size(), m = s2.size(), t = s3.size();
  if (n + m != t) {
    return false;
  }
  std::vector<bool> f(m + 1, false);
  f[0] = true;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= m; ++j) {
      int p = i + j - 1;
      if (i > 0) {
        f[j] = f[j] && s1[i - 1] == s3[p];
      }
      if (j > 0) {
        f[j] = f[j] || (f[j - 1] && s2[j - 1] == s3[p]);
      }
    }
  }
  return f[m];
}

int main() {
  std::string s1 = "aabcc";
  std::string s2 = "dbbca";
  std::string s3 = "aadbbcbcac";
  std::cout << "Is interleaving: "
            << (isInterleave(s1, s2, s3) ? "true" : "false") << std::endl;
  return 0;
}

package main

func isInterleave(s1 string, s2 string, s3 string) bool {
	n, m, t := len(s1), len(s2), len(s3)
	if (n + m) != t {
		return false
	}
	f := make([]bool, m+1)
	f[0] = true
	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			p := i + j - 1
			if i > 0 {
				f[j] = f[j] && s1[i-1] == s3[p]
			}
			if j > 0 {
				f[j] = f[j] || f[j-1] && s2[j-1] == s3[p]
			}
		}
	}
	return f[m]
}

#include <iostream>
#include <string>
#include <vector>

int numDistinct(const std::string &s, const std::string &t) {
  int m = s.size(), n = t.size();
  if (m < n) {
    return 0;
  }
  std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
  for (int i = 0; i <= m; ++i) {
    dp[i][n] = 1;
  }
  for (int i = m - 1; i >= 0; --i) {
    for (int j = n - 1; j >= 0; --j) {
      if (s[i] == t[j]) {
        dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
      } else {
        dp[i][j] = dp[i + 1][j];
      }
    }
  }
  return dp[0][0];
}

int main() {
  std::string s = "rabbbit";
  std::string t = "rabbit";
  std::cout << "Number of distinct subsequences: " << numDistinct(s, t)
            << std::endl;
  return 0;
}

package main

func numDistinct(s, t string) int {
	m, n := len(s), len(t)
	if m < n {
		return 0
	}
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][n] = 1
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if s[i] == t[j] {
				dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
			} else {
				dp[i][j] = dp[i+1][j]
			}
		}
	}
	return dp[0][0]
}

#include <iostream>
#include <vector>

int uniquePaths(int m, int n) {
  std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
  for (int i = 0; i < m; ++i) {
    dp[i][0] = 1;
  }
  for (int j = 0; j < n; ++j) {
    dp[0][j] = 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];
}

int main() {
  int m = 3, n = 7;
  std::cout << "Number of unique paths: " << uniquePaths(m, n) << std::endl;
  return 0;
}

package main

func uniquePaths(m, n int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][0] = 1
	}
	for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

#include <algorithm>
#include <iostream>
#include <vector>

int min(int x, int y) { return (x < y) ? x : y; }

int minPathSum(const std::vector<std::vector<int>> &grid) {
  if (grid.empty() || grid[0].empty()) {
    return 0;
  }
  int rows = grid.size(), columns = grid[0].size();
  std::vector<std::vector<int>> dp(rows, std::vector<int>(columns, 0));
  dp[0][0] = grid[0][0];
  for (int i = 1; i < rows; ++i) {
    dp[i][0] = dp[i - 1][0] + grid[i][0];
  }
  for (int j = 1; j < columns; ++j) {
    dp[0][j] = dp[0][j - 1] + grid[0][j];
  }
  for (int i = 1; i < rows; ++i) {
    for (int j = 1; j < columns; ++j) {
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
  return dp[rows - 1][columns - 1];
}

int main() {
  std::vector<std::vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
  std::cout << "Minimum path sum: " << minPathSum(grid) << std::endl;
  return 0;
}

package main

func minPathSum(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	rows, columns := len(grid), len(grid[0])
	dp := make([][]int, rows)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, columns)
	}
	dp[0][0] = grid[0][0]
	for i := 1; i < rows; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for j := 1; j < columns; j++ {
		dp[0][j] = dp[0][j-1] + grid[0][j]
	}
	for i := 1; i < rows; i++ {
		for j := 1; j < columns; j++ {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
		}
	}
	return dp[rows-1][columns-1]
}

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int min(int x, int y) { return (x < y) ? x : y; }

int minimumTotal(const std::vector<std::vector<int>> &triangle) {
  int n = triangle.size();
  std::vector<std::vector<int>> f(n, std::vector<int>(n, 0));
  f[0][0] = triangle[0][0];
  for (int i = 1; i < n; ++i) {
    f[i][0] = f[i - 1][0] + triangle[i][0];
    for (int j = 1; j < i; ++j) {
      f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
    }
    f[i][i] = f[i - 1][i - 1] + triangle[i][i];
  }
  int ans = INT_MAX;
  for (int i = 0; i < n; ++i) {
    ans = min(ans, f[n - 1][i]);
  }
  return ans;
}

int main() {
  std::vector<std::vector<int>> triangle = {
      {2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
  std::cout << "Minimum total path sum: " << minimumTotal(triangle)
            << std::endl;
  return 0;
}

package main

import "math"

func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	f := make([][]int, n)
	for i := 0; i < n; i++ {
		f[i] = make([]int, n)
	}
	f[0][0] = triangle[0][0]
	for i := 1; i < n; i++ {
		f[i][0] = f[i-1][0] + triangle[i][0]
		for j := 1; j < i; j++ {
			f[i][j] = min(f[i-1][j-1], f[i-1][j]) + triangle[i][j]
		}
		f[i][i] = f[i-1][i-1] + triangle[i][i]
	}
	ans := math.MaxInt32
	for i := 0; i < n; i++ {
		ans = min(ans, f[n-1][i])
	}
	return ans
}

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

bool canPartition(std::vector<int> &nums) {
  int n = nums.size();
  if (n < 2) {
    return false;
  }

  int sum = std::accumulate(nums.begin(), nums.end(), 0);
  int maxNum = *std::max_element(nums.begin(), nums.end());
  if (sum % 2 != 0) {
    return false;
  }

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

  std::vector<std::vector<bool>> dp(n, std::vector<bool>(target + 1, false));
  for (int i = 0; i < n; ++i) {
    dp[i][0] = true;
  }
  dp[0][nums[0]] = true;
  for (int i = 1; i < n; ++i) {
    int v = nums[i];
    for (int j = 1; j <= target; ++j) {
      if (j >= v) {
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - v];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n - 1][target];
}

int main() {
  std::vector<int> nums = {1, 5, 11, 5};
  std::cout << "Can partition: " << (canPartition(nums) ? "true" : "false")
            << std::endl;
  return 0;
}

package main

func canPartition(nums []int) bool {
	n := len(nums)
	if n < 2 {
		return false
	}

	sum, max := 0, 0
	for _, v := range nums {
		sum += v
		if v > max {
			max = v
		}
	}
	if sum%2 != 0 {
		return false
	}

	target := sum / 2
	if max > target {
		return false
	}

	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, target+1)
	}
	for i := 0; i < n; i++ {
		dp[i][0] = true
	}
	dp[0][nums[0]] = true
	for i := 1; i < n; i++ {
		v := nums[i]
		for j := 1; j <= target; j++ {
			if j >= v {
				dp[i][j] = dp[i-1][j] || dp[i-1][j-v]
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[n-1][target]
}

#include <iostream>
#include <vector>

void backtrack(const std::vector<int> &nums, int target, int index, int sum,
               int &count) {
  if (index == nums.size()) {
    if (sum == target) {
      count++;
    }
    return;
  }
  backtrack(nums, target, index + 1, sum + nums[index], count);
  backtrack(nums, target, index + 1, sum - nums[index], count);
}

int findTargetSumWays(const std::vector<int> &nums, int target) {
  int count = 0;
  backtrack(nums, target, 0, 0, count);
  return count;
}

int main() {
  std::vector<int> nums = {1, 1, 1, 1, 1};
  int target = 3;
  std::cout << "Number of ways to reach target sum: "
            << findTargetSumWays(nums, target) << std::endl;
  return 0;
}

package main

func findTargetSumWays(nums []int, target int) (count int) {
	var backtrack func(int, int)
	backtrack = func(index, sum int) {
		if index == len(nums) {
			if sum == target {
				count++
			}
			return
		}
		backtrack(index+1, sum+nums[index])
		backtrack(index+1, sum-nums[index])
	}
	backtrack(0, 0)
	return
}

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int min(int a, int b) { return (a < b) ? a : b; }

int coinChange(const std::vector<int> &nums, int target) {
  std::vector<int> dp(target + 1, INT_MAX);
  dp[0] = 0;
  for (int num : nums) {
    for (int i = 0; i <= target - num; ++i) {
      if (dp[i] == INT_MAX) {
        continue;
      }
      dp[i + num] = min(dp[i + num], dp[i] + 1);
    }
  }
  return dp[target] == INT_MAX ? -1 : dp[target];
}

int main() {
  std::vector<int> nums = {1, 2, 5};
  int target = 11;
  std::cout << "Minimum coins needed: " << coinChange(nums, target)
            << std::endl;
  return 0;
}

package main

import "math"

func coinChange(nums []int, target int) int {
	dp := make([]int, target+1)
	for i := 1; i <= target; i++ {
		dp[i] = math.MaxInt32
	}
	for _, num := range nums {
		for i := 0; i <= target-num; i++ {
			if dp[i] == math.MaxInt32 {
				continue
			}
			dp[i+num] = min(dp[i+num], dp[i]+1)
		}
	}
	if dp[target] == math.MaxInt32 {
		return -1
	}
	return dp[target]
}

#include <iostream>
#include <vector>

int combinationSum4(const std::vector<int> &nums, int target) {
  std::vector<int> dp(target + 1, 0);
  dp[0] = 1;
  for (int i = 1; i <= target; ++i) {
    for (int num : nums) {
      if (num <= i) {
        dp[i] += dp[i - num];
      }
    }
  }
  return dp[target];
}

int main() {
  std::vector<int> nums = {1, 2, 3};
  int target = 4;
  std::cout << "Number of combinations: " << combinationSum4(nums, target)
            << std::endl;
  return 0;
}

package main

func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1
	for i := 1; i <= target; i++ {
		for _, num := range nums {
			if num <= i {
				dp[i] += dp[i-num]
			}
		}
	}
	return dp[target]
}

#include <iostream>
#include <vector>

int getArea(std::vector<std::vector<int>> &grid,
            std::vector<std::vector<bool>> &visited, int i, int j) {
  int m = grid.size(), n = grid[0].size();
  if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 || visited[i][j]) {
    return 0;
  }
  visited[i][j] = true;
  return getArea(grid, visited, i - 1, j) + getArea(grid, visited, i + 1, j) +
         getArea(grid, visited, i, j - 1) + getArea(grid, visited, i, j + 1) +
         1;
}

int maxAreaOfIsland(std::vector<std::vector<int>> &grid) {
  int m = grid.size(), n = grid[0].size();
  std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
  int ans = 0;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      int area = getArea(grid, visited, i, j);
      if (area > ans) {
        ans = area;
      }
    }
  }
  return ans;
}

int main() {
  std::vector<std::vector<int>> grid = {
      {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
      {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
      {0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
  std::cout << "Maximum area of island: " << maxAreaOfIsland(grid) << std::endl;
  return 0;
}

package main

func maxAreaOfIsland(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	visited := make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	var getArea func(int, int) int
	getArea = func(i, j int) int {
		if i < 0 || i == m || j < 0 || j == n {
			return 0
		}
		if grid[i][j] == 0 || visited[i][j] {
			return 0
		}
		visited[i][j] = true
		return getArea(i-1, j) + getArea(i+1, j) + getArea(i, j-1) + getArea(i, j+1) + 1
	}
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			area := getArea(i, j)
			if area > ans {
				ans = area
			}
		}
	}
	return ans
}

#include <functional>
#include <iostream>
#include <vector>

const int UNCOLOR = 0, RED = 1, GREEN = 2;

bool isBipartite(const std::vector<std::vector<int>> &graph) {
  int n = graph.size();
  std::vector<int> state(n, UNCOLOR);
  bool valid = true;

  std::function<void(int, int)> dfs = [&](int idx, int color) -> void {
    int necolor = (color == RED) ? GREEN : RED;
    state[idx] = color;

    for (int ne : graph[idx]) {
      if (state[ne] == UNCOLOR) {
        dfs(ne, necolor);
      } else {
        valid = (necolor == state[ne]);
      }

      if (!valid) {
        return;
      }
    }
  };

  for (int i = 0; i < n && valid; ++i) {
    if (state[i] == UNCOLOR) {
      dfs(i, RED);
    }
  }
  return valid;
}

int main() {
  std::vector<std::vector<int>> graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
  std::cout << "Is bipartite: " << (isBipartite(graph) ? "true" : "false")
            << std::endl;
  return 0;
}

package main

var (
	UNCOLOR, RED, GREEN = 0, 1, 2
)

func isBipartite(graph [][]int) bool {
	n := len(graph)

	state := make([]int, n)
	valid := true

	var dfs func(idx, color int)
	dfs = func(idx, color int) {
		necolor := RED
		if color == RED {
			necolor = GREEN
		}
		state[idx] = color

		for _, ne := range graph[idx] {
			if state[ne] == UNCOLOR {
				dfs(ne, necolor)
			} else {
				valid = necolor == state[ne]
			}

			if !valid {
				return
			}
		}
	}

	for i := 0; i < n && valid; i++ {
		if state[i] == UNCOLOR {
			dfs(i, RED)
		}
	}
	return valid
}

#include <iostream>
#include <queue>
#include <vector>

std::vector<std::vector<int>> updateMatrix(std::vector<std::vector<int>> &mat) {
  int m = mat.size();
  int n = mat[0].size();
  std::vector<std::vector<int>> res(m, std::vector<int>(n, 0));
  std::vector<int> dx = {1, 0, -1, 0};
  std::vector<int> dy = {0, -1, 0, 1};
  std::queue<std::pair<int, int>> queue;

  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if (mat[i][j] == 0) {
        queue.push({i, j});
      }
    }
  }

  while (!queue.empty()) {
    int x = queue.front().first;
    int y = queue.front().second;
    queue.pop();
    for (int k = 0; k < 4; ++k) {
      int nx = x + dx[k];
      int ny = y + dy[k];
      if (nx >= 0 && ny >= 0 && nx < m && ny < n && mat[nx][ny] == 1) {
        if (res[nx][ny] == 0 || res[x][y] + 1 < res[nx][ny]) {
          res[nx][ny] = res[x][y] + 1;
          queue.push({nx, ny});
        }
      }
    }
  }

  return res;
}

int main() {
  std::vector<std::vector<int>> mat = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
  std::vector<std::vector<int>> result = updateMatrix(mat);
  for (const auto &row : result) {
    for (int val : row) {
      std::cout << val << " ";
    }
    std::cout << std::endl;
  }
  return 0;
}

package main

func updateMatrix(mat [][]int) [][]int {
	m := len(mat)
	n := len(mat[0])
	res := make([][]int, m)
	for i := range res {
		res[i] = make([]int, n)
	}
	dx := []int{1, 0, -1, 0}
	dy := []int{0, -1, 0, 1}
	var queue [][]int
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if mat[i][j] == 0 {
				queue = append(queue, []int{i, j})
			}
		}
	}
	for len(queue) > 0 {
		x := queue[0][0]
		y := queue[0][1]
		queue = queue[1:]
		for k := 0; k < 4; k++ {
			nx := x + dx[k]
			ny := y + dy[k]
			if nx >= 0 && ny >= 0 && nx < m && ny < n && mat[nx][ny] == 1 {
				if res[nx][ny] == 0 || res[x][y]+1 < res[nx][ny] {
					res[nx][ny] = res[x][y] + 1
					queue = append(queue, []int{nx, ny})
				}
			}
		}
	}
	return res
}

#include <climits>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

int ladderLength(const std::string &beginWord, const std::string &endWord,
                 std::vector<std::string> &wordList) {
  std::unordered_map<std::string, int> wordId;
  std::vector<std::vector<int>> graph;
  int idCounter = 0;

  auto addWord = [&](std::string word) -> int {
    if (wordId.find(word) == wordId.end()) {
      wordId[word] = idCounter++;
      graph.push_back({});
    }
    return wordId[word];
  };

  auto addEdge = [&](std::string word) -> int {
    int id1 = addWord(word);
    std::string s = word;
    for (size_t i = 0; i < s.size(); ++i) {
      char originalChar = s[i];
      s[i] = '*';
      int id2 = addWord(s);
      graph[id1].push_back(id2);
      graph[id2].push_back(id1);
      s[i] = originalChar;
    }
    return id1;
  };

  for (const auto &word : wordList) {
    addEdge(word);
  }
  int beginId = addEdge(beginWord);
  if (wordId.find(endWord) == wordId.end()) {
    return 0;
  }
  int endId = wordId[endWord];

  const int inf = INT_MAX;
  std::vector<int> dist(wordId.size(), inf);
  dist[beginId] = 0;
  std::queue<int> queue;
  queue.push(beginId);

  while (!queue.empty()) {
    int v = queue.front();
    queue.pop();
    if (v == endId) {
      return dist[endId] / 2 + 1;
    }
    for (int w : graph[v]) {
      if (dist[w] == inf) {
        dist[w] = dist[v] + 1;
        queue.push(w);
      }
    }
  }
  return 0;
}

int main() {
  std::vector<std::string> wordList = {"hot", "dot", "dog",
                                       "lot", "log", "cog"};
  std::string beginWord = "hit";
  std::string endWord = "cog";
  std::cout << "Ladder length: " << ladderLength(beginWord, endWord, wordList)
            << std::endl;
  return 0;
}

package main

import "math"

func ladderLength(beginWord string, endWord string, wordList []string) int {
	wordId := map[string]int{}
	graph := [][]int{}
	addWord := func(word string) int {
		id, has := wordId[word]
		if !has {
			id = len(wordId)
			wordId[word] = id
			graph = append(graph, []int{})
		}
		return id
	}
	addEdge := func(word string) int {
		id1 := addWord(word)
		s := []byte(word)
		for i, b := range s {
			s[i] = '*'
			id2 := addWord(string(s))
			graph[id1] = append(graph[id1], id2)
			graph[id2] = append(graph[id2], id1)
			s[i] = b
		}
		return id1
	}

	for _, word := range wordList {
		addEdge(word)
	}
	beginId := addEdge(beginWord)
	endId, has := wordId[endWord]
	if !has {
		return 0
	}

	const inf int = math.MaxInt64
	dist := make([]int, len(wordId))
	for i := range dist {
		dist[i] = inf
	}
	dist[beginId] = 0
	queue := []int{beginId}
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]
		if v == endId {
			return dist[endId]/2 + 1
		}
		for _, w := range graph[v] {
			if dist[w] == inf {
				dist[w] = dist[v] + 1
				queue = append(queue, w)
			}
		}
	}
	return 0
}

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

int openLock(std::vector<std::string> &deadends, std::string target) {
  if (target == "0000") {
    return 0;
  }

  std::unordered_set<std::string> deadendsSet(deadends.begin(), deadends.end());
  if (deadendsSet.count(target) || deadendsSet.count("0000")) {
    return -1;
  }

  std::unordered_set<std::string> visit;

  auto getnei = [](std::string state) -> std::vector<std::string> {
    std::vector<std::string> res;
    std::string s = state;
    for (int i = 0; i < 4; ++i) {
      char ch = s[i];
      s[i] = ch + 1;
      if (s[i] > '9') {
        s[i] = '0';
      }
      res.push_back(s);

      s[i] = ch - 1;
      if (s[i] < '0') {
        s[i] = '9';
      }
      res.push_back(s);

      s[i] = ch;
    }
    return res;
  };

  std::queue<std::string> queue;
  queue.push("0000");
  int step = 0;
  while (!queue.empty()) {
    int size = queue.size();
    for (int i = 0; i < size; ++i) {
      std::string state = queue.front();
      queue.pop();
      for (const auto &ne : getnei(state)) {
        if (!visit.count(ne) && !deadendsSet.count(ne)) {
          if (ne == target) {
            return step + 1;
          }
          visit.insert(ne);
          queue.push(ne);
        }
      }
    }
    ++step;
  }
  return -1;
}

int main() {
  std::vector<std::string> deadends = {"0201", "0101", "0102", "1212", "2002"};
  std::string target = "0202";
  std::cout << "Minimum turns to open lock: " << openLock(deadends, target)
            << std::endl;
  return 0;
}

package main

func openLock(deadends []string, target string) int {
	if target == "0000" {
		return 0
	}

	deadendsSet := map[string]bool{}
	for _, item := range deadends {
		deadendsSet[item] = true
	}
	if deadendsSet[target] || deadendsSet["0000"] {
		return -1
	}

	visit := map[string]bool{}

	getnei := func(state string) []string {
		res := []string{}
		s := []byte(state)
		for i, ch := range s {
			s[i] = ch + 1
			if s[i] > '9' {
				s[i] = '0'
			}
			res = append(res, string(s))

			s[i] = ch - 1
			if s[i] < '0' {
				s[i] = '9'
			}
			res = append(res, string(s))

			s[i] = ch
		}
		return res
	}

	queue := []string{"0000"}
	step := 0
	for len(queue) > 0 {
		newqueue := []string{}
		for _, state := range queue {
			for _, ne := range getnei(state) {
				if !visit[ne] && !deadendsSet[ne] {
					if ne == target {
						return step + 1
					}
					visit[ne] = true
					newqueue = append(newqueue, ne)
				}
			}
		}
		queue = newqueue
		step++
	}
	return -1
}

#include <iostream>
#include <vector>

void dfs(const std::vector<std::vector<int>> &graph, std::vector<int> &stk,
         std::vector<std::vector<int>> &ans, int x) {
  if (x == graph.size() - 1) {
    ans.push_back(stk);
    return;
  }
  for (int y : graph[x]) {
    stk.push_back(y);
    dfs(graph, stk, ans, y);
    stk.pop_back();
  }
}

std::vector<std::vector<int>>
allPathsSourceTarget(const std::vector<std::vector<int>> &graph) {
  std::vector<std::vector<int>> ans;
  std::vector<int> stk = {0};
  dfs(graph, stk, ans, 0);
  return ans;
}

int main() {
  std::vector<std::vector<int>> graph = {{1, 2}, {3}, {3}, {}};
  std::vector<std::vector<int>> result = allPathsSourceTarget(graph);
  for (const auto &path : result) {
    for (int node : path) {
      std::cout << node << " ";
    }
    std::cout << std::endl;
  }
  return 0;
}

package main

func allPathsSourceTarget(graph [][]int) (ans [][]int) {
	stk := []int{0}
	var dfs func(int)
	dfs = func(x int) {
		if x == len(graph)-1 {
			ans = append(ans, append([]int{}, stk...))
			return
		}
		for _, y := range graph[x] {
			stk = append(stk, y)
			dfs(y)
			stk = stk[:len(stk)-1]
		}
	}
	dfs(0)
	return
}

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

struct Edge {
  int to;
  double weight;
};

std::vector<double>
calcEquation(const std::vector<std::vector<std::string>> &equations,
             const std::vector<double> &values,
             const std::vector<std::vector<std::string>> &queries) {
  std::unordered_map<std::string, int> id;
  int idCounter = 0;

  for (const auto &eq : equations) {
    const std::string &a = eq[0];
    const std::string &b = eq[1];
    if (id.find(a) == id.end()) {
      id[a] = idCounter++;
    }
    if (id.find(b) == id.end()) {
      id[b] = idCounter++;
    }
  }

  std::vector<std::vector<Edge>> graph(idCounter);
  for (size_t i = 0; i < equations.size(); ++i) {
    int v = id[equations[i][0]];
    int w = id[equations[i][1]];
    graph[v].push_back({w, values[i]});
    graph[w].push_back({v, 1.0 / values[i]});
  }

  auto bfs = [&](int start, int end) -> double {
    std::vector<double> ratios(idCounter, 0.0);
    ratios[start] = 1.0;
    std::queue<int> queue;
    queue.push(start);

    while (!queue.empty()) {
      int v = queue.front();
      queue.pop();
      if (v == end) {
        return ratios[v];
      }
      for (const auto &e : graph[v]) {
        if (ratios[e.to] == 0.0) {
          ratios[e.to] = ratios[v] * e.weight;
          queue.push(e.to);
        }
      }
    }
    return -1.0;
  };

  std::vector<double> ans(queries.size());
  for (size_t i = 0; i < queries.size(); ++i) {
    const std::string &startStr = queries[i][0];
    const std::string &endStr = queries[i][1];
    if (id.find(startStr) == id.end() || id.find(endStr) == id.end()) {
      ans[i] = -1.0;
    } else {
      ans[i] = bfs(id[startStr], id[endStr]);
    }
  }
  return ans;
}

int main() {
  std::vector<std::vector<std::string>> equations = {{"a", "b"}, {"b", "c"}};
  std::vector<double> values = {2.0, 3.0};
  std::vector<std::vector<std::string>> queries = {
      {"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
  std::vector<double> result = calcEquation(equations, values, queries);
  for (double val : result) {
    std::cout << val << " ";
  }
  std::cout << std::endl;
  return 0;
}

package main

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	// 给方程组中的每个变量编号
	id := map[string]int{}
	for _, eq := range equations {
		a, b := eq[0], eq[1]
		if _, has := id[a]; !has {
			id[a] = len(id)
		}
		if _, has := id[b]; !has {
			id[b] = len(id)
		}
	}

	// 建图
	type edge struct {
		to     int
		weight float64
	}
	graph := make([][]edge, len(id))
	for i, eq := range equations {
		v, w := id[eq[0]], id[eq[1]]
		graph[v] = append(graph[v], edge{w, values[i]})
		graph[w] = append(graph[w], edge{v, 1 / values[i]})
	}

	bfs := func(start, end int) float64 {
		ratios := make([]float64, len(graph))
		ratios[start] = 1
		queue := []int{start}
		for len(queue) > 0 {
			v := queue[0]
			queue = queue[1:]
			if v == end {
				return ratios[v]
			}
			for _, e := range graph[v] {
				if w := e.to; ratios[w] == 0 {
					ratios[w] = ratios[v] * e.weight
					queue = append(queue, w)
				}
			}
		}
		return -1
	}

	ans := make([]float64, len(queries))
	for i, q := range queries {
		start, hasS := id[q[0]]
		end, hasE := id[q[1]]
		if !hasS || !hasE {
			ans[i] = -1
		} else {
			ans[i] = bfs(start, end)
		}
	}
	return ans
}

#include <iostream>
#include <queue>
#include <vector>

std::vector<std::pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int rows, columns;

int longestIncreasingPath(std::vector<std::vector<int>> &matrix) {
  if (matrix.empty() || matrix[0].empty()) {
    return 0;
  }
  rows = matrix.size();
  columns = matrix[0].size();
  std::vector<std::vector<int>> outdegrees(rows, std::vector<int>(columns, 0));

  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < columns; ++j) {
      for (const auto &dir : dirs) {
        int newRow = i + dir.first;
        int newColumn = j + dir.second;
        if (newRow >= 0 && newRow < rows && newColumn >= 0 &&
            newColumn < columns && matrix[newRow][newColumn] > matrix[i][j]) {
          outdegrees[i][j]++;
        }
      }
    }
  }

  std::queue<std::pair<int, int>> queue;
  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < columns; ++j) {
      if (outdegrees[i][j] == 0) {
        queue.push({i, j});
      }
    }
  }

  int ans = 0;
  while (!queue.empty()) {
    ans++;
    int size = queue.size();
    for (int i = 0; i < size; ++i) {
      auto cell = queue.front();
      queue.pop();
      int row = cell.first;
      int column = cell.second;
      for (const auto &dir : dirs) {
        int newRow = row + dir.first;
        int newColumn = column + dir.second;
        if (newRow >= 0 && newRow < rows && newColumn >= 0 &&
            newColumn < columns &&
            matrix[newRow][newColumn] < matrix[row][column]) {
          outdegrees[newRow][newColumn]--;
          if (outdegrees[newRow][newColumn] == 0) {
            queue.push({newRow, newColumn});
          }
        }
      }
    }
  }
  return ans;
}

int main() {
  std::vector<std::vector<int>> matrix = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
  std::cout << "Longest increasing path: " << longestIncreasingPath(matrix)
            << std::endl;
  return 0;
}

package main

var (
	dirs = [][2]int{
		{-1, 0},
		{1, 0},
		{0, -1},
		{0, 1},
	}
	rows, columns int
)

func longestIncreasingPath(matrix [][]int) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}
	rows, columns = len(matrix), len(matrix[0])
	outdegrees := make([][]int, rows)
	for i := 0; i < rows; i++ {
		outdegrees[i] = make([]int, columns)
	}
	for i := 0; i < rows; i++ {
		for j := 0; j < columns; j++ {
			for _, dir := range dirs {
				newRow, newColumn := i+dir[0], j+dir[1]
				if newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[i][j] {
					outdegrees[i][j]++
				}
			}
		}
	}

	queue := [][]int{}
	for i := 0; i < rows; i++ {
		for j := 0; j < columns; j++ {
			if outdegrees[i][j] == 0 {
				queue = append(queue, []int{i, j})
			}
		}
	}
	ans := 0
	for len(queue) != 0 {
		ans++
		size := len(queue)
		for i := 0; i < size; i++ {
			cell := queue[0]
			queue = queue[1:]
			row, column := cell[0], cell[1]
			for _, dir := range dirs {
				newRow, newColumn := row+dir[0], column+dir[1]
				if newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] < matrix[row][column] {
					outdegrees[newRow][newColumn]--
					if outdegrees[newRow][newColumn] == 0 {
						queue = append(queue, []int{newRow, newColumn})
					}
				}
			}
		}
	}
	return ans
}

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> findOrder(int numCourses,
                           std::vector<std::vector<int>> &prerequisites) {
  std::vector<std::vector<int>> edges(numCourses);
  std::vector<int> indeg(numCourses, 0);
  std::vector<int> result;

  for (const auto &info : prerequisites) {
    edges[info[1]].push_back(info[0]);
    indeg[info[0]]++;
  }

  std::queue<int> q;
  for (int i = 0; i < numCourses; ++i) {
    if (indeg[i] == 0) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    result.push_back(u);
    for (int v : edges[u]) {
      indeg[v]--;
      if (indeg[v] == 0) {
        q.push(v);
      }
    }
  }

  if (result.size() != numCourses) {
    return {};
  }
  return result;
}

int main() {
  int numCourses = 4;
  std::vector<std::vector<int>> prerequisites = {
      {1, 0}, {2, 0}, {3, 1}, {3, 2}};
  std::vector<int> order = findOrder(numCourses, prerequisites);
  for (int course : order) {
    std::cout << course << " ";
  }
  std::cout << std::endl;
  return 0;
}

package main

func findOrder(numCourses int, prerequisites [][]int) []int {
	var (
		edges  = make([][]int, numCourses)
		indeg  = make([]int, numCourses)
		result []int
	)

	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
		indeg[info[0]]++
	}

	q := []int{}
	for i := 0; i < numCourses; i++ {
		if indeg[i] == 0 {
			q = append(q, i)
		}
	}

	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		result = append(result, u)
		for _, v := range edges[u] {
			indeg[v]--
			if indeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	if len(result) != numCourses {
		return []int{}
	}
	return result
}

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

std::string alienOrder(const std::vector<std::string> &words) {
  std::unordered_map<char, std::vector<char>> g;
  std::unordered_map<char, int> inDeg;
  for (char c : words[0]) {
    inDeg[c] = 0;
  }

  for (size_t i = 1; i < words.size(); ++i) {
    const std::string &s = words[i - 1];
    const std::string &t = words[i];
    for (char c : t) {
      inDeg[c] += 0;
    }
    for (size_t j = 0; j < s.size() && j < t.size(); ++j) {
      if (s[j] != t[j]) {
        g[s[j]].push_back(t[j]);
        inDeg[t[j]]++;
        break;
      }
    }
    if (s.size() > t.size() && s.substr(0, t.size()) == t) {
      return "";
    }
  }

  std::string order;
  std::queue<char> q;
  for (const auto &[u, d] : inDeg) {
    if (d == 0) {
      q.push(u);
    }
  }

  while (!q.empty()) {
    char u = q.front();
    q.pop();
    order.push_back(u);
    for (char v : g[u]) {
      if (--inDeg[v] == 0) {
        q.push(v);
      }
    }
  }

  if (order.size() != inDeg.size()) {
    return "";
  }
  return order;
}

int main() {
  std::vector<std::string> words = {"wrt", "wrf", "er", "ett", "rftt"};
  std::string result = alienOrder(words);
  std::cout << "Alien dictionary order: " << result << std::endl;
  return 0;
}

package main

func alienOrder(words []string) string {
	g := map[byte][]byte{}
	inDeg := map[byte]int{}
	for _, c := range words[0] {
		inDeg[byte(c)] = 0
	}
next:
	for i := 1; i < len(words); i++ {
		s, t := words[i-1], words[i]
		for _, c := range t {
			inDeg[byte(c)] += 0
		}
		for j := 0; j < len(s) && j < len(t); j++ {
			if s[j] != t[j] {
				g[s[j]] = append(g[s[j]], t[j])
				inDeg[t[j]]++
				continue next
			}
		}
		if len(s) > len(t) {
			return ""
		}
	}

	order := make([]byte, len(inDeg))
	q := order[:0]
	for u, d := range inDeg {
		if d == 0 {
			q = append(q, u)
		}
	}
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		for _, v := range g[u] {
			if inDeg[v]--; inDeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	if cap(q) == 0 {
		return string(order)
	}
	return ""
}

#include <iostream>
#include <queue>
#include <vector>

bool sequenceReconstruction(const std::vector<int> &nums,
                            const std::vector<std::vector<int>> &sequences) {
  int n = nums.size();
  std::vector<std::vector<int>> g(n + 1);
  std::vector<int> inDeg(n + 1, 0);

  for (const auto &sequence : sequences) {
    for (size_t i = 1; i < sequence.size(); ++i) {
      int x = sequence[i - 1];
      int y = sequence[i];
      g[x].push_back(y);
      inDeg[y]++;
    }
  }

  std::queue<int> q;
  for (int i = 1; i <= n; ++i) {
    if (inDeg[i] == 0) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    if (q.size() > 1) {
      return false;
    }
    int x = q.front();
    q.pop();
    for (int y : g[x]) {
      if (--inDeg[y] == 0) {
        q.push(y);
      }
    }
  }

  return true;
}

int main() {
  std::vector<int> nums = {1, 2, 3};
  std::vector<std::vector<int>> sequences = {{1, 2}, {1, 3}};
  std::cout << "Can reconstruct sequence: "
            << (sequenceReconstruction(nums, sequences) ? "true" : "false")
            << std::endl;
  return 0;
}

package main

func sequenceReconstruction(nums []int, sequences [][]int) bool {
	n := len(nums)
	g := make([][]int, n+1)
	inDeg := make([]int, n+1)
	for _, sequence := range sequences {
		for i := 1; i < len(sequence); i++ {
			x, y := sequence[i-1], sequence[i]
			g[x] = append(g[x], y)
			inDeg[y]++
		}
	}

	q := []int{}
	for i := 1; i <= n; i++ {
		if inDeg[i] == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		if len(q) > 1 {
			return false
		}
		x := q[0]
		q = q[1:]
		for _, y := range g[x] {
			if inDeg[y]--; inDeg[y] == 0 {
				q = append(q, y)
			}
		}
	}
	return true
}

#include <iostream>
#include <vector>

int find(std::vector<int> &parent, int x) {
  if (parent[x] != x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
}

void unionSets(std::vector<int> &parent, int from, int to) {
  parent[find(parent, from)] = find(parent, to);
}

int findCircleNum(const std::vector<std::vector<int>> &isConnected) {
  int n = isConnected.size();
  std::vector<int> parent(n);
  for (int i = 0; i < n; ++i) {
    parent[i] = i;
  }

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (isConnected[i][j] == 1) {
        unionSets(parent, i, j);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (parent[i] == i) {
      ++ans;
    }
  }
  return ans;
}

int main() {
  std::vector<std::vector<int>> isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
  std::cout << "Number of provinces: " << findCircleNum(isConnected)
            << std::endl;
  return 0;
}

package main

func findCircleNum(isConnected [][]int) (ans int) {
	n := len(isConnected)
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	union := func(from, to int) {
		parent[find(from)] = find(to)
	}

	for i, row := range isConnected {
		for j := i + 1; j < n; j++ {
			if row[j] == 1 {
				union(i, j)
			}
		}
	}
	for i, p := range parent {
		if i == p {
			ans++
		}
	}
	return
}

#include <iostream>
#include <string>
#include <vector>

class UnionFind {
public:
  UnionFind(int n) : parent(n), size(n, 1), setCount(n) {
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
    }
  }

  int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  void unionSets(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy)
      return;
    if (size[fx] < size[fy])
      std::swap(fx, fy);
    size[fx] += size[fy];
    parent[fy] = fx;
    --setCount;
  }

  bool inSameSet(int x, int y) { return find(x) == find(y); }

  int getSetCount() const { return setCount; }

private:
  std::vector<int> parent;
  std::vector<int> size;
  int setCount;
};

bool isSimilar(const std::string &s, const std::string &t) {
  int diff = 0;
  for (size_t i = 0; i < s.size(); ++i) {
    if (s[i] != t[i]) {
      ++diff;
      if (diff > 2) {
        return false;
      }
    }
  }
  return true;
}

int numSimilarGroups(const std::vector<std::string> &strs) {
  int n = strs.size();
  UnionFind uf(n);
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (!uf.inSameSet(i, j) && isSimilar(strs[i], strs[j])) {
        uf.unionSets(i, j);
      }
    }
  }
  return uf.getSetCount();
}

int main() {
  std::vector<std::string> strs = {"tars", "rats", "arts", "star"};
  std::cout << "Number of similar groups: " << numSimilarGroups(strs)
            << std::endl;
  return 0;
}

package main

type unionFind struct {
	parent, size []int
	setCount     int // 当前连通分量数目
}

func newUnionFind(n int) *unionFind {
	parent := make([]int, n)
	size := make([]int, n)
	for i := range parent {
		parent[i] = i
		size[i] = 1
	}
	return &unionFind{parent, size, n}
}

func (uf *unionFind) find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *unionFind) union(x, y int) {
	fx, fy := uf.find(x), uf.find(y)
	if fx == fy {
		return
	}
	if uf.size[fx] < uf.size[fy] {
		fx, fy = fy, fx
	}
	uf.size[fx] += uf.size[fy]
	uf.parent[fy] = fx
	uf.setCount--
}

func (uf *unionFind) inSameSet(x, y int) bool {
	return uf.find(x) == uf.find(y)
}

func isSimilar(s, t string) bool {
	diff := 0
	for i := range s {
		if s[i] != t[i] {
			diff++
			if diff > 2 {
				return false
			}
		}
	}
	return true
}

func numSimilarGroups(strs []string) int {
	n := len(strs)
	uf := newUnionFind(n)
	for i, s := range strs {
		for j := i + 1; j < n; j++ {
			if !uf.inSameSet(i, j) && isSimilar(s, strs[j]) {
				uf.union(i, j)
			}
		}
	}
	return uf.setCount
}

#include <iostream>
#include <vector>

int find(std::vector<int> &parent, int x) {
  if (parent[x] != x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
}

bool unionSets(std::vector<int> &parent, int from, int to) {
  int x = find(parent, from);
  int y = find(parent, to);
  if (x == y) {
    return false;
  }
  parent[x] = y;
  return true;
}

std::vector<int>
findRedundantConnection(const std::vector<std::vector<int>> &edges) {
  std::vector<int> parent(edges.size() + 1);
  for (size_t i = 0; i < parent.size(); ++i) {
    parent[i] = i;
  }

  for (const auto &edge : edges) {
    if (!unionSets(parent, edge[0], edge[1])) {
      return edge;
    }
  }
  return {};
}

int main() {
  std::vector<std::vector<int>> edges = {{1, 2}, {1, 3}, {2, 3}};
  std::vector<int> result = findRedundantConnection(edges);
  std::cout << "Redundant connection: [" << result[0] << ", " << result[1]
            << "]" << std::endl;
  return 0;
}

package main

func findRedundantConnection(edges [][]int) []int {
	parent := make([]int, len(edges)+1)
	for i := range parent {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	union := func(from, to int) bool {
		x, y := find(from), find(to)
		if x == y {
			return false
		}
		parent[x] = y
		return true
	}
	for _, e := range edges {
		if !union(e[0], e[1]) {
			return e
		}
	}
	return nil
}

#include <iostream>
#include <unordered_set>
#include <vector>

int longestConsecutive(const std::vector<int> &nums) {
  std::unordered_set<int> numSet(nums.begin(), nums.end());
  int longestStreak = 0;

  for (int num : numSet) {
    if (numSet.find(num - 1) == numSet.end()) {
      int currentNum = num;
      int currentStreak = 1;

      while (numSet.find(currentNum + 1) != numSet.end()) {
        currentNum++;
        currentStreak++;
      }

      longestStreak = std::max(longestStreak, currentStreak);
    }
  }

  return longestStreak;
}

int main() {
  std::vector<int> nums = {100, 4, 200, 1, 3, 2};
  std::cout << "Longest consecutive sequence length: "
            << longestConsecutive(nums) << std::endl;
  return 0;
}

package main

func longestConsecutive(nums []int) int {
	numSet := map[int]bool{}
	for _, num := range nums {
		numSet[num] = true
	}
	longestStreak := 0
	for num := range numSet {
		if !numSet[num-1] {
			currentNum := num
			currentStreak := 1
			for numSet[currentNum+1] {
				currentNum++
				currentStreak++
			}
			if longestStreak < currentStreak {
				longestStreak = currentStreak
			}
		}
	}
	return longestStreak
}