class Solution {
    // 滑动窗口
    // 使用set判断无重复
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        Set<Character> set = new HashSet<Character>();

        int left = 0;

        for (int right=0; right<s.length(); right++) {
            while (left <= right && set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(s.charAt(right));
            ans = Math.max(right - left + 1, ans);
        }

        return ans;
    }
}

class Solution {
    // 使用双指针，每一次移动height较小的那个指针
    // 因为如果移动大的，高度变小，长度也变小，肯定不会有更大的出现
    public int maxArea(int[] height) {
        int left = 0, right = height.length-1;
        int ans = 0;

        while (left < right) {
            ans = Math.max(Math.min(height[left], height[right]) * (right - left), ans);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
}

class Solution {
    // 确定一个数的情况下，另外两个可以用双指针
    // 一个从i+1，一个从n-1开始，根据三数之和判断谁移动
    // 由于不能重复，所以需要判断第一个和第二个的重复性
    // 保证第一第二，就能保证第三个不重复
    public List<List<Integer>> threeSum(int[] nums) {
        // 先需要给数组排序
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();

        for (int i=0; i<nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1]) { continue; } // 重复跳过
            int j = i+1, k = nums.length - 1;

            while(j < k) {
                // 注意，每个元素自己不能重复，两个-1这样是可以的
                while (j > i+1 && j < k && nums[j] == nums[j-1]) { j++; } // j重复的也跳过
                if (j >= k) { break; }
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    list.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                } else if (sum < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }

        return list;
    }
}

class Solution {
    // 还是确定一个，然后另外两个双指针
    // 而且不用判断重复
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];

        for (int i=0; i<nums.length; i++) {
            int j = i + 1, k = nums.length - 1;

            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                ans = Math.abs(target - ans) > Math.abs(target - sum) ? sum : ans;

                if (sum == target) {
                    return ans;
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }

        return ans;
    }
}

class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);

        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);

            // 因为肯定有，所以不会越界
            if (nums[mid] == nums[mid+1]) {
                return nums[mid];
            } else if (nums[mid] < mid+1) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}

/**
* O(logn)，二分查找
* 此处数组不是完全有序的
* 但是，两段分别有序，而且有一个关键点，后面一段有序的，全部小于等于nums[0]
* 第一段有序的，也都是大于等于nums[0]
*/
class Solution {
  public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    // 后面有很多nums[0]跟别的的判断，所以此处先是直接判断nums[0]是否等于target
    if (nums[0] == target) { return 0; }

    while (left <= right) {
      int mid = left + ((right - left) >> 1);
      if (nums[mid] == target) {
        return mid;
      } else {
        if (nums[0] > nums[mid]) { // nums[mid]在后面一段
          if (nums[mid] < target && target <= nums[nums.length - 1]) {
            left = mid + 1;
          } else {
            right = mid - 1;
          }
        } else { // mid在前面一段
          if (nums[0] <= target && target < nums[mid]) {
            right = mid - 1;
          } else {
            left = mid + 1;
          }
        }
      }
    }

    return -1;
  }
}

/**
* O(logn)，二分查找
* 此处数组不是完全有序的
* 但是，两段分别有序，而且有一个关键点，后面一段有序的，全部小于等于nums[0]
* 第一段有序的，也都是大于等于nums[0]
*/
class Solution {
  public boolean search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    // 后面有很多nums[0]跟别的的判断，所以此处先是直接判断nums[0]是否等于target
    if (nums[0] == target) { return true; }

    while (left <= right) {
      int mid = left + ((right - left) >> 1);
      if (nums[mid] == target) {
        return true;
      }

      // 此处与前面那个的区别是，若left和mid和right都相等，那么判断不了是在哪个区见
      // 所以，将left和right各自缩短，然后用新的区间去判断，所以nums[0]都要编程nums[lefts]
      if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
        left++;
        right--;
      } else if (nums[left] > nums[mid]) { // nums[mid]在后面一段
        if (nums[mid] < target && target <= nums[nums.length - 1]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      } else { // mid在前面一段
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      }
    }

    return false;
  }
}

class Solution {
    public int findMin(int[] nums) {
        // 看最后一个，如果mid大于最后，那么那么是第一段有序的，需要到右边去
        int left = 0, right = nums.length - 1, len = nums.length;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            // 等号，就是判断了，数组只有一个的情况
            if (nums[mid] <= nums[len - 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 使用这个，注意left是会有等于nums.length的边界问题的
        return nums[left];
    }
}

class Solution {
    // 包含重复元素
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1, len = nums.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            // 注意此处只要每次是与numsright比就好了
            // 注意此处比较的时候出来的问题， 每次跟最后那个len比，最后那个是需要变化的
            if (nums[mid] == nums[len]) {
                right -= 1; // 如果相等，那么把最后的一位移到前面即可
                len = right;
            } else if (nums[mid] > nums[len]) {
                left = mid + 1;
            } else {
                right = mid - 1;
                len = mid;
            }
        }

        // 注意，每次用left和right的时候都要考虑下出界问题
        return nums[left];
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) { return new int[]{-1, -1}; }
        int[] ans = new int[2];
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 如果相等的话，需要right往左走
            // 所以此处再加上nums[mid] >= target
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 非常注意，像上面有等号的，最终都会left>right，所以left可能为最大长度出界，而right可能为-1出界
        if (left == nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }
        ans[0] = left;
        
      
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if (right == -1 || nums[right] != target) {
            return new int[]{-1, -1}; 
        }
        ans[1] = right;

        return ans;
    }
}

// 未验证
import java.util.*;

public class XiuBu {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();

        scanner.nextLine();
        int[] a = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        // 注意，去重复，distinct()
        // 注意，此处升序其实不用这么麻烦，只是告诉你sorted里面也可以那样写，而且不能写在后面，因为maptoint返回IntStream，还是基本类型int，所以不能写
        int[] b = Arrays.stream(scanner.nextLine().split(" ")).distinct().
                sorted((x, y) -> Integer.parseInt(x) - Integer.parseInt(y)).mapToInt(Integer::valueOf).toArray();

        long ans = 0;

        // 对于每一个坏的地方ai，找出b中第一个大于等于的
        for (int i = 0; i < n; i++) {
            int left = 0, right = m;
            while (left <= right) {
                int mid = (left + (right - left >> 1));

                if (b[mid] == a[i]) {
                    left = right = mid;
                    break;
                } else if (b[mid] > a[i]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 有相等，就是相等
            // 没有相等，目前到了left > right，nums[left] > target，nums[right] < target
            // 没有相等，然后由于left > right，所以left可能右边出界，right可能左边出界
            // 这里估计肯定有，所以不考虑left出界的情况
            ans += b[left];
        }

        System.out.println(ans);
    }
}

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        // 每一次，都需要找到离nums2[i]最近的nums1中的数
        // 如何找，使用二分

        long sum = 0;
        // sum直接每一次的绝对值差相加，所以此处要找到多减去的最多的
        long duoJianQuMax = 0;
        int[] sortedNums1 = nums1.clone();
        Arrays.sort(sortedNums1);

        for (int i=0; i< sortedNums1.length; i++) {
            int a = nums1[i], b = nums2[i]; // 注意此处还是nums1
            if (a == b) { // 注意相等
                continue;
            }
            int x = Math.abs(a - b);
            sum += x;

            int left = 0, right = sortedNums1.length - 1;
            while (left <= right) {
                int mid = (left + ((right - left) >> 1));
                if (sortedNums1[mid] <= b) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            int c = Integer.MAX_VALUE; // 注意取最小值
            if (left != sortedNums1.length) {
                c = Math.abs(b - sortedNums1[left]);
            }
            if (right != -1) {
                c = Math.min(Math.abs(b - sortedNums1[right]), c);
            }

            if (c < x) {
                duoJianQuMax = Math.max(duoJianQuMax, x - c);
            }
        }

        return (int)((sum - duoJianQuMax) % (1e9+7));
    }
}

// 注意，记忆这一个，简单一点
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length-1;

        // 返回第一个>=target的
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                left = mid; // 因为最终left是结果，所以直接这样了，当然此处return mid也是可以的
                break;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
			
      	// 因为while中使用的是<=，所以在不是等于的情况下，最终形态left = right + 1
      	// 即，nums[right] < target < nums[left]，所以要插入的位置就是在left处
      	// 因为left初始化是0，所以插入0的位置也是可以的（right=-1）；插入nums.length也是可以的，right没动过的情况下。
        return left;
    }
}

// 同样的代码
// 只不过可能不同的理解而已
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        // 返回将会被插入的位置
        // 此处没有重复元素，当然有重复元素也能做，看34.
        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // left最后得到的范围是0～nums.length
        // 所以说，最小的话，正好插在最开始，最大的话，正好加载最末尾
        return left;
    }
}

public boolean searchMatrix(int[][] matrix, int target) {
  // 根据该特性，可以使用二分，看作二叉搜索树实现
  int row = 0, col = matrix[0].length - 1;

  while (true) {
    if (matrix[row][col] == target) {
      return true;
    } else if (matrix[row][col] > target) {
      col -= 1;
      if (col < 0) {
        break;
      }
    } else {
      row += 1;
      if (row >= matrix.length) {
        break;
      }
    }
  }

  return false;
}

class Solution {
    /**
    使用二分查找（找节点）+位运算（顺着路径找节点）
     */
    public int countNodes(TreeNode root) {
        if (root == null) { return 0; }
        int height = getHeight(root, 0);
        int left = (int) Math.pow(2, height-1), right = (int) Math.pow(2, height) - 1;

        while (left <= right) {
            // 根据二进制位看顺着那一条路径，最高位是1，不看
            int mid = left + ((right - left) >> 1);
            TreeNode node = root;
            // 顺着路径下来
            for (int i=height-2; i>=0; i--) {
                if (((mid >> i) & 1) == 1) {
                    node = node.right;
                } else {
                    node = node.left;
                }
            }
            if (node == null) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
    }

        return right;
    }

    public int getHeight(TreeNode node, int height) {
        if (node == null) {
            return height;
        }

        return Math.max(getHeight(node.left, height + 1), getHeight(node.right, height + 1));
    }
}

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        
        Arrays.sort(nums);
        int[] sums = new int[nums.length + 1];

        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int target = queries[i];
            int left = 1, right = sums.length - 1;

            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (sums[mid] == target) {
                     left = right = mid;
                     break;
                }else if (sums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            ans[i] = right;
        }

        return ans;
    }
}

class Solution {
    // 使用滑动窗口
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0, ans = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];

            while (left <= right && sum >= target) {
                // 注意，这个滑动窗口的结果的实现有点小小的特殊，是在while里面判断的
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left];
                left += 1;
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // 滑动窗口
        // 每一次枚举右端点，然后看左端点啥时候不满足
        int mul = 1, ans = 0;
        int n = nums.length, left = 0;

        for (int right=0; right<n; right++) {
            mul *= nums[right];                  // 每一次枚举一下右端点

            while (left <= right && mul >= k) {  // 右端点加1之后，如果有超过，那么左边+1，直到满足条件
                mul /= nums[left];
                left++;
            }

            ans += right - left + 1;             // left和right都算在内
        }

        return ans;
    }
}

class Solution {
    public int longestSubstring(String s, int k) {
        // 滑动窗口，但是该滑动窗口不满足二段性质，因为次数都要大于等于
        // 所以增加性质，1～26个字符的限制，那么每一次都是要小于等于该字符种类，满足
        char[] chars = s.toCharArray();
        int n = chars.length;
        int ans = 0;

        // 对每一次的种类个数，进行滑动窗口
        for (int p = 1; p <= 26; p++) {
            
            int left = 0;
            int zhonglei = 0; // 目前字符种类个数
            int kZhonglei = 0; // 目前达到k次的字符种类个数
            int[] nums = new int[26]; // 26个字符的个数统计
            
            for (int right = 0; right < n; right++) {
                int index = chars[right] - 'a';
                nums[index] += 1;
                if (nums[index] == 1) { zhonglei += 1; } // 多一个种类
                if (nums[index] == k) { kZhonglei += 1; }

                while (left < right && zhonglei > p) {
                    int tempIndex = chars[left] - 'a';
                    nums[tempIndex] -= 1;
                    if (nums[tempIndex] == 0) {
                        zhonglei -= 1;
                    }
                    if (nums[tempIndex] == k - 1) {
                        kZhonglei -= 1;
                    }
                    left += 1;
                }

                // 上面弄下来，会满足zhobnglei这个变量是在p个数内的
                // 然后我下面只要判断里面的所有种类都是出现了至少k次的就行了
                if (kZhonglei == zhonglei) {
                    ans = Math.max(ans, right - left + 1);
                }
            }
        }

        return ans;
    }
}

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = Math.min(s.length(), t.length()), left = 0;
        int ans = 0, cost  = 0;

        // 枚举right，找到最先满足的最小left
        for (int right = 0; right < n; right++) {
            cost += Math.abs(s.charAt(right) - t.charAt(right));
            while (left <= right && cost > maxCost) {
                cost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }

            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();

        int left = 0, changeNum = 0, ans = 0;

        // 'T'变'F'
        for (int right = 0; right < n; right++) {        // right变后可能不满足
            if (answerKey.charAt(right) == 'T') {
                changeNum++;
            }

            while (left <= right && changeNum > k) {     // 找到满足的最小left
                if (answerKey.charAt(left) == 'T') {
                    changeNum--;
                }
                left++;
            }
            
            ans = Math.max(ans, right - left + 1);
        }

        changeNum = 0; left = 0;
        // 'F'变'T'
        for (int right = 0; right < n; right++) {        // right变后可能不满足
            if (answerKey.charAt(right) == 'F') {
                changeNum++;
            }

            while (left <= right && changeNum > k) {     // 找到满足的最小left
                if (answerKey.charAt(left) == 'F') {
                    changeNum--;
                }
                left++;
            }
            
            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}

// 注意两点，left和right都是算在内的
// 一开始while的时候，left<=right，然后先判断，再对left+1，因为一开始的left是算在内的
class Solution {
    public int characterReplacement(String s, int k) {
        int ans = 0;

        for (int m = 0; m<26; m++) {
            int left = 0;
            int changeCount = 0;

            for (int right = 0; right < s.length(); right++) {
                if (s.charAt(right) != m + 'A') {
                    changeCount++;
                }
                while (left <= right && changeCount > k) {  // 找到能满足的最小的left，
                    if (s.charAt(left) != m + 'A') {
                        changeCount--;
                    }
                    left++;
                }
                ans = Math.max(ans, right - left + 1);
            }
        }

        return ans;
    }
}

class Solution {
    // 先把所有没生气的顾客都加上，然后对应的customers[i]都变为0
    // 然后滑动窗口为minute的，看哪一个最大，这个就不用延伸minute两边了
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int ans = 0;
        for (int i=0; i<customers.length; i++) {
            if (grumpy[i] == 0) {
                ans += customers[i];
                customers[i] = 0;
            }
        }

        int sum = 0, nextAns = 0, left = 0;
        for (int right = 0; right < customers.length; right++) {
            sum += customers[right];

            while (right - left > minutes-1) {
                sum -= customers[left];
                left += 1;
            }
            nextAns = Math.max(sum, nextAns);
        }

        return ans + nextAns;
    }
}

class Solution {
    /**
    使用滑动窗口 + 优先队列
    优先队列的话，由于中位数，k是偶数的时候可能需要两个，所以使用两个优先队列
    一个存在小的一半，一份存放大的一半
    由于可能k为基数，所以可以让left多一个，然后每次都跟left这个队列比较
     */
    public double[] medianSlidingWindow(int[] nums, int k) {
        Queue<Integer> left = new PriorityQueue<Integer>((x, y) -> (Integer.compare(x, y)));
        Queue<Integer> right = new PriorityQueue<Integer>((x, y) -> (Integer.compare(y, x)));

        // right是从大到小的，left是从小到大的
        for (int i=0; i<k; i++) {
            left.offer(nums[i]);
        }
        for (int i=0; i<k/2; i++) { // right可能比left少1，所以后面每次跟left比较
            right.offer(left.poll());
        }

        double[] ans = new double[nums.length - k + 1];
        ans[0] = getMid(k, left, right);
        // left存放的是大的那一半，从小到大
        // right存放的是小的那一半，从大到小
        for (int i=k; i<nums.length; i++) { // 滑动窗口开始滑动
            int add = nums[i], del = nums[i-k];
            if (add >= left.peek()) {
                left.offer(add);
            } else {
                right.offer(add);
            }
            if (del >= left.peek()) {
                left.remove(del); // 注意这个删除是O(n)级别的
            } else {
                right.remove(del);
            }

            adjust(left, right);
            ans[i - k + 1] = getMid(k, left, right);
        }

        return ans;
    }

    public void adjust(Queue<Integer> left, Queue<Integer> right) { // 每次调整两个队列的个数
        while (right.size() > left.size()) { left.offer(right.poll()); }
        while (left.size() - 1 > right.size()) { right.offer(left.poll()); }
    }

    public double getMid(int k, Queue<Integer> left, Queue<Integer> right) {
        if (k % 2 == 0) {
            return left.peek() * 1.0 / 2 + right.peek() * 1.0 / 2; // 防止溢出
        } else {
            return left.peek() * 1.0;
        }
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 滑动窗口，此处用set好像不太行啊，只能用hashmap记录个数了
        int ans = 0;
        int left = 0;
        // Set<Character> set = new HashSet<>();
        Map<Character, Integer> map = new HashMap<>();

        for (int right = 0; right<s.length(); right++) {
            char c = s.charAt(right);
            map.put(c, map.getOrDefault(c, 0) + 1);
            
            while (left <= right && map.get(c) > 1) {
                char temp = s.charAt(left);
                map.put(temp, map.getOrDefault(temp, 0) - 1);
                left += 1;
            }
            
            ans = Math.max(right - left + 1, ans);
        }

        return ans;
    }
}

class Solution {
    // 滑动窗口最大值
    // 使用堆，然后存的时候同时存上下标，那么取出最大的时候，若这个最大值根据下表判断不在里面的话，直接扔掉
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] - a[0]);

        int[] ans = new int[n - k + 1];
        for (int i = 0; i < k-1; i ++) {
            queue.offer(new int[]{nums[i], i});
        }
        for (int i = k-1; i < n; i++) {
            queue.offer(new int[]{nums[i], i});

            while (queue.peek()[1] < i - k + 1) { queue.poll(); }

            ans[i-k+1] = (queue.peek()[0]);        
        }

        return ans;
    }
}

/**
* 邻接表 + 拓扑排序
* 有钱的指向钱少的，然后每一次更新被指向的那个节点的ans，更新的是和指向的节点的ans比小的
* 因为指向的的人前比那个人多，所以被指向的ans要么自己和所有邻居的ans中的最小的
* 当然也可以使用dfs（没钱指向有钱），递归更新ans
*/
class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[] g = new ArrayList[n];
        int[] inCnts = new int[n];
        int[] ans = new int[n];  // 注意初始化

        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
            // *******注意这个初始化，一开始肯定是自己啊
            ans[i] = i;    
        }

        for (int i = 0; i < richer.length; i++) {
            int a = richer[i][0], b = richer[i][1];
            g[a].add(b);
            inCnts[b] += 1;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (inCnts[i] == 0) {
                queue.offerLast(i);
            }
        }

        while (!queue.isEmpty()) {
            int a = queue.pollFirst();
            for (int b: g[a]) {
                inCnts[b] -= 1;
                if (inCnts[b] == 0) {
                    queue.offerLast(b);
                }

                // a -> b，a的钱肯定比b多，那么更新b的答案
                // *******非常注意这里，不是与a这个有点的quiet比就好了
                // *******而是看ans[a]，因为比a大的，肯定也比b大
                if (quiet[ans[b]] > quiet[ans[a]]) {
                    ans[b] = ans[a];
                }
            }
        }

        return ans;
    }
}

// 注意：这一题，就是1～k放在的行和列的排序都有了，怎样让他们表示在二维矩阵里面
// 先pos[row[i]] = i;
// 再ans[pos[col[i]]][i] = col[i];
// 其中pos[col[i]]表示，在第i列的数在第几行。

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        // 这是拓扑排序之后的两个，单独拓扑，然后后面放进去
        int[] row = tuopu(k, rowConditions), col = tuopu(k, colConditions);

        if (row.length < k || col.length < k) {
            return new int[][]{};
        }

        int[][] ans = new int[k][k];

        int[] pos = new int[k + 1];

        // 表示1～k分别放在哪一行
        for (int i = 0; i < k; i++) {
            // row[i]放第i行
            pos[row[i]] = i;
        }

        // 注意：这一题，就是1～k放在的行和列的排序都有了，怎样让他们表示在二维矩阵里面
        // 先pos[row[i]] = i;
        // 再ans[pos[col[i]]][i] = col[i];
        // 其中pos[col[i]]表示，在第i列的数在第几行。
        // 表示1～k分别放在哪里
        for (int i = 0; i < k; i++) {
            ans[pos[col[i]]][i] = col[i];
        }

        return ans;
    }

    public int[] tuopu(int n, int[][] conditions) {
        List<Integer>[] g = new ArrayList[n + 1];
        int[] inDe = new int[n + 1];
        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            g[i] = new ArrayList<>();
        }

        for (int[] edge: conditions) {
            int u = edge[0], v = edge[1];
            g[u].add(v);
            inDe[v] += 1;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (inDe[i] == 0) {
                queue.offerLast(i);
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            ans.add(u);

            for (int v: g[u]) {
                if (--inDe[v] == 0) {
                    queue.offerLast(v);
                }
            }
        }

        return ans.stream().mapToInt(Integer::valueOf).toArray();
    }
}

// 其实可以理解成一个图中是否存在环
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 使用拓扑排序
        List<Integer>[] g = new ArrayList[numCourses];
        int[] inDe = new int[numCourses];
        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int[] temp = prerequisites[i];
            g[temp[1]].add(temp[0]);
            inDe[temp[0]] += 1;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDe[i] == 0) {
                queue.offerLast(i);
                ans.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int temp = queue.pollLast();
            for (int nei: g[temp]) {
                inDe[nei] -= 1;
                if (inDe[nei] == 0) {
                    queue.offerLast(nei);
                    ans.add(nei);
                }
            }
        }

        return ans.size() == numCourses;
    }
}

/**
 * 两数相加
 *
 * @author jcwang
 */
public class TemplateLianbiao{
    public static void main(String[] args) {
        Solution solution = new TemplateLianbiao().new Solution();
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public ListNode solve(ListNode l) {
            return new ListNode();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = l1, pre = null;

        int carry = 0;
        int value1 = 0;
        while (l1 != null && l2 != null) {
          value1 = l1.val + l2.val + carry;
          l1.val = value1 % 10;
          carry = value1 / 10;
          pre = l1;
          l1 = l1.next;
          l2 = l2.next;
        }

        if (l2 != null) {
          pre.next = l2;

          while (l2 != null) {
            value1 = l2.val + carry;
            l2.val = value1 % 10;
            carry = value1 / 10;
            pre = l2;
            l2 = l2.next;
          }
        } else if (l1 != null) {
          while (l1 != null) {
            value1 = l1.val + carry;
            l1.val = value1 % 10;
            carry = value1 / 10;
            pre = l1;
            l1 = l1.next;
          }
        }
        // 两个都没有了
        if (carry == 1) {
          pre.next = new ListNode(1);
        }

        return head;
        }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 使用哑节点
        ListNode dummy = new ListNode(0, head);
        ListNode right = head, left = dummy;

        for (int i=0; i<n; i++) {
            // 链表长度小于n
            if (right == null) {
                return head;
            }
            right = right.next;
        }

        while (right != null) {
            right = right.next;
            left = left.next;
        }
        left.next = left.next.next;

        return dummy.next;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode pre = dummy;

        // 每一次选择最k个链表中最小的一个进行穿针，使用priorityqueue实现
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((t1, t2) -> (t1.val - t2.val));
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(node);
            }
        }

        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            pre.next = node;
            if (node.next != null) {
                queue.offer(node.next);
            }
            pre = pre.next;
        }

        return dummy.next;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        // 注意此处的prev不要指向head，会出先环的，直接为null就好
        ListNode prev = null;
        ListNode cur = head;

        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }

        return prev;
    }
}

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter.next = head;
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;
        iter.next = null;
        return ret;
    }
}

// 注意，此处不需要哑节点
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 不需要用到前一个节点的索引，直接用head.next.next
        // ListNode prev = head;
        //  注意head可能本身为null的情况
        if (head == null) return null;

        ListNode start = head;

        // 此处是head与head.next比较，所以要判断head.next是否非空
        while(head.next != null) {
            if (head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }

        return start;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 由于第一个节点可能会被删除，所以需要用一个哑节点
        ListNode dummyNode = new ListNode(-1, head);

        ListNode node = dummyNode;
        while (node.next != null && node.next.next != null) {
            if (node.next.val == node.next.next.val) {
                int x = node.next.val;    // 用x暂时记录相等的值
                while (node.next != null && node.next.val == x) {
                    node.next = node.next.next;
                }
            } else {
                node = node.next;
            }
        }

        return dummyNode.next;
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) return head;

        ListNode preLeftNode = null, preRight = null, cur = head;
        for (int i=0; i<left-2; i++) {
            cur = cur.next;
        }
        preLeftNode = left == 1 ? null : cur; // left左边一个
        
        cur = left == 1 ? cur : cur.next; // 第left个
        ListNode leftNode = cur;
        ListNode tempNext = cur.next;

        for (int i=left; i<right; i++) {
            ListNode temp = tempNext.next;
            tempNext.next = cur;
            cur = tempNext;
            tempNext = temp;
        }

        // tempNext是right后面的一个节点
        if (preLeftNode == null) head = cur;
        else preLeftNode.next = cur;
        leftNode.next = tempNext;

        return head;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        // 先全部复制一遍，放在每个节点的后面，再将random节点指上去，然后拆开
        if (head == null) { return null; }
        
        Node start = head;

        // 复制
        while (head != null) {
            Node node = new Node(head.val);
            node.next = head.next;
            head.next = node;
            
            head = head.next.next;
        }

        // 复制随机指针
        head = start;
        while (head != null) {
            if (head.random != null) {
                head.next.random = head.random.next;
            }

            head = head.next.next;
        }

        // 拆开
        head = start;
        Node ans = head.next;
        while (head != null) {
            Node temp = head.next;

            head.next = head.next.next;
            if (head.next != null) {
                temp.next = head.next.next;
            }

            head = head.next;
        }

        return ans;
    }
} 
// 第二个方法有点秀的
public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        Node cur = head;
        HashMap<Node,Node> map = new HashMap<>();
        while(cur!=null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }

// 使用双指针，pa和pb，若pa遍历完则指向headB开头，pb同。如果两个指针同时只想一个节点或者同时指向null。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      	if (headA == null || headB == null) {
            return null;
        }
      
        ListNode ptr1 = headA, ptr2 = headB;

        // 同时指向同一个节点，或者同时为空
      	// 注意，null也是一种状态的，不能马上跳过，只不过null的下一个是什么，就自己判断一下
        while (ptr1 != ptr2) {
            if (ptr1 == null) {
                ptr1 = headB;
            } else {
                ptr1 = ptr1.next;
            }
            if (ptr2 == null) {
                ptr2 = headA;
            } else {
                ptr2 = ptr2.next;
            }
        }

        return ptr1;
    }
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;

        while (pre.next != null) {
            if (pre.next.val == val) {
                pre.next = pre.next.next;
            } else {
                pre = pre.next;
            }
        }

        return dummy.next;
    }
}

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] ans = new ListNode[k];

        ListNode start = head;
        int length = 0;
        while (start != null) {
            start = start.next;
            length += 1;
        }

        int num = length / k;
        int yu = length % k;

        
        for (int i=0; i<k; i++) {
            ans[i] = head;
            for (int j=0; j<num+(i>yu-1?0:1) - 1; j++) {
                if (head != null) {
                    head = head.next;
                } else {
                    break;
                }
            }
            if (head != null) {
                ListNode temp = head;
                head = head.next;
                temp.next = null;
            }
        }

        return ans;
    }
}