import java.util.*;

public class Main {
    /**
     * 整数除法
     * @param dividend
     * @param divisor
     * @return
     */
    public int divide(int dividend,int divisor) {
        if(dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        int neg = 2; // 是不是负数
        if(dividend > 0) {
            dividend = -dividend;
            neg --;
        }
        if(divisor > 0) {
            divisor = -divisor;
            neg --;
        }
        int res = 0;
        while (dividend <= divisor) {
            int value = divisor;
            int quotient = 1;
            while (value >= Integer.MIN_VALUE>>1 && dividend <= (value << 1)) {
                value = value << 1;
                quotient = quotient << 1;
            }
            res += quotient;
            dividend -= value;
        }
        return neg == 1 ? -res : res;
    }

    /**
     * 二进制加法
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0; // 进位
        while (i >= 0 || j >= 0 || carry > 0) {
            int digitA = i >= 0 ? a.charAt(i--) - '0' : 0;
            int digitB = j >= 0 ? b.charAt(j--) - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum / 2;
            res.append(sum % 2);
        }
        return res.reverse().toString();
    }

    /**
     * 前n个数字二进制形式中1的个数
     * @param num
     * @return
     */
    public int[] countBits(int num) {
//        int[] result = new int[num + 1];
//        for (int i = 0; i <= num; i++) {
//            int j = i;
//            while (j != 0) {
//                result[i]++;
//                j = j & (j-1); // 去掉最右边的1
//            }
//        }
//        return result;
        // 根据i&(i-1) 计算i的二进制形式中1的个数
//        int[] result = new int[num + 1];
//        for (int i = 1; i <= num; i++) {
//            result[i] = result[i & (i-1)] + 1;
//        }
//        return result;
        // 根据i/2 计算i的二进制形式中1的个数
        int[] result = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            result[i] = result[i >> 1] + (i & 1);
        }
        return result;
    }

    /**
     * 只出现一次的数字
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        // 一个数是由32个0或1组成的，如果把每个出现3次的数字的同一位相加，则最后的结果一定可以被3整除
        // 因为每一位只有0和1，所以相加的结果只可能是0或3，一定可以被3整除
        // 把数组中每个数字的同一位都相加，只要结果不能被3整除，那么只出现一次的那个数字的这一位一定是1，反之就是0
        int[] bitSums = new int[32]; // 每一位的和
        for (int num: nums) {
            for (int i = 0; i < 32; i++) {
                bitSums[i] += (num >> (31 - i)) & 1; // 得到每一位的值
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = (res << 1) + bitSums[i] % 3; // 只可能是0或者1
        }
        return res;
    }

    /**
     * 单词长度的最大乘积
     * @param words
     * @return
     */
    public int maxProduct(String[] words) {
//        boolean[][] flags = new boolean[words.length][26];
//        for (int i = 0; i < words.length; i++) {
//            for (char c: words[i].toCharArray()) {
//                flags[i][c-'a'] = true;
//            }
//        }
//        int res = 0;
//        for (int i = 0; i < words.length; i++) {
//            for (int j = i+1; j < words.length; j++) {
//                int k = 0;
//                while (k < 26) {
//                    if(flags[i][k] && flags[j][k]) {
//                        break;
//                    }
//                    k++;
//                }
//                if(k == 26) {
//                    int prod = words[i].length() * words[j].length();
//                    res = Math.max(res,prod);
//                }
//            }
//        }
//        return res;
        int[] flags = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            for (char ch: words[i].toCharArray()) {
                flags[i] |= 1 << (ch - 'a');
            }
        }
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if((flags[i] & flags[j]) == 0) {
                    int prod = words[i].length()*words[j].length();
                    res = Math.max(res,prod);
                }
            }
        }
        return res;
    }

    /**
     * 排序数组中的两个数字之和
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers,int target) {
        int i = 0;
        int j = numbers.length - 1;
        while (i < j) {
            if(numbers[i] + numbers[j] < target) {
                i ++;
            } else if (numbers[i] + numbers[j] > target){
                j --;
            } else {
                return new int[]{i,j};
            }
        }
        return new int[]{-1,-1};
    }

    /**
     * 数组中和为0的3个数字
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int i = 0;
        while (i < nums.length - 2) {
            twoSum(nums,i,res);
            int tmp = nums[i];
            while (i < nums.length && nums[i] == tmp) {
                i ++;
            }
        }
        return res;
    }
    private void twoSum(int[] nums,int i,List<List<Integer>> ans) {
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            if(nums[i] + nums[j] + nums[k] == 0) {
                ans.add(Arrays.asList(nums[i],nums[j],nums[k]));

                int tmp = nums[j];
                while (nums[j] == tmp && j < k) {
                    ++j; // 跳过重复的部分
                }
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                ++j;
            } else {
                --k;
            }
        }
    }

    /**
     * 和大于或等于k的最短子数组
     * @param k
     * @param nums
     * @return
     */
    public int minSubArrayLen(int k,int[] nums) {
        int l = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        for (int r = 0; r < nums.length; r++) {
            sum += nums[r];
            while (l <= r && sum >= k) {
                minLen = Math.min(minLen,r - l + 1);
                sum -= nums[l++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    /**
     * 乘积小于k的子数组
     * @param nums
     * @param k
     * @return
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        long product = 1;
        int left = 0;
        int count = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (left <= right && product >= k) {
                product /= nums[left++];
            }
            count += right >= left ? right - left + 1 : 0;
        }
        return count;
    }

    /**
     * 和为k的子数组
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        Map<Integer,Integer> map = new HashMap<>();
        int count = 0;
        map.put(0,1);
        for (int num: nums) {
            sum += num;
            count += map.getOrDefault(sum-k,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;
    }

    /**
     * 0和1个数相同的子数组
     * @param nums
     * @return
     */
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>(); // 和为j的最小索引
        int sum = 0;
        int maxLen = 0;
        map.put(0,-1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i] != 0 ? 1 : -1;
            if(map.containsKey(sum)) {
                maxLen = Math.max(maxLen,i - map.get(sum));
            } else {
                map.put(sum,i);
            }
        }
        return maxLen;
    }

    /**
     * 左右两边子数组的和相等
     * @param nums
     * @return
     */
    public int pivotIndex(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(sum - nums[i] == total - sum) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二维子矩阵的数字之和
     */
    class NumMatrix {
        private int[][] sums;
        public NumMatrix(int[][] matrix) {
            if(matrix.length == 0 || matrix[0].length == 0) {
                return;
            }

            sums = new int[matrix.length+1][matrix[0].length+1];
            for (int i = 0; i < matrix.length; i++) {
                int rowSum = 0;
                for (int j = 0; j < matrix[0].length; j++) {
                    rowSum += matrix[i][j];
                    sums[i+1][j + 1] = sums[i][j + 1] + rowSum;
                }
            }
        }

        public 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];
        }
    }

    /**
     * 字符串中的变位词
     * @param s1
     * @param s2
     * @return
     */
    public boolean checkInclusion(String s1,String s2) {
        int[] counts = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
            counts[s2.charAt(i) - 'a']--;
        }
        if(areAllZero(counts)) {
            return true;
        }
        for (int i = s1.length(); i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
            counts[s2.charAt(i - s1.length()) - 'a']++; // 把之前减掉的加上
            if(areAllZero(counts)) {
                return true;
            }
        }
        return false;
    }
    private boolean areAllZero(int[] counts) {
        for (int num : counts) {
            if(num != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 字符串中的所有变为词
     * @param s1
     * @param s2
     * @return
     */
    public List<Integer> findAnagrams(String s1, String s2) {
        List<Integer> indices = new LinkedList<>();
        if(s1.length() < s2.length()) {
            return indices;
        }

        int[] counts = new int[26];
        int i = 0;
        for (; i < s1.length(); i++) {
            counts[s2.charAt(i) - 'a']++;
            counts[s1.charAt(i) - 'a']--;
        }
        if(areAllZero(counts)) {
            indices.add(0);
        }
        for(;i < s1.length(); ++i) {
            counts[s1.charAt(i) - 'a']--;
            counts[s1.charAt(i - s2.length()) - 'a']++;
            if (areAllZero(counts)) {
                indices.add(i - s2.length() + 1);
            }
        }
        return indices;
    }

    /**
     * 不含重复字符的最长子字符串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
//        int n = s.length();
//        int[] pos = new int[256]; // 字符 a 最右边出现的索引位置
//        Arrays.fill(pos,-1);
//        int ans = 0;
//        for (int i = 0; i < s.length(); i++) {
//            int j = i - 1;
//            while (j > pos[s.charAt(i)]) {
//                if(j != pos[s.charAt(j)]) {
//                    break;
//                }
//                j--;
//            }
//            ans = Math.max(ans,i - j + 1);
//            pos[s.charAt(i)] = i;
//        }
//        return ans;
//        if(s.length() == 0) {
//            return 0;
//        }
//        int[] counts = new int[256];
//        int i = 0;
//        int j = -1;
//        int ans = 1;
//        for (;i < s.length(); i++) {
//            counts[s.charAt(i)] ++;
//            while (hasGreaterThan1(counts)) {
//                ++ j;
//                counts[s.charAt(j)] --;
//            }
//            ans = Math.max(ans,i - j);
//        }
//        return ans;
        if(s.length() == 0) {
            return 0;
        }
        int[] counts = new int[256];
        int i = 0;
        int j = -1;
        int ans = 0;
        int countDup = 0;
        for (; i < s.length(); i++) {
            counts[s.charAt(i)] ++;
            if(counts[s.charAt(i)] == 2) {
                countDup ++;
            }
            while (countDup > 0) {
                j ++;
                counts[s.charAt(j)] --;
                if(counts[s.charAt(j)] == 1) {
                    countDup --;
                }
            }
            ans = Math.max(i - j,ans);
        }
        return ans;
    }
    private boolean hasGreaterThan1 (int[] counts) {
        for (int count : counts) {
            if(count > 1) {
                return true;
            }
        }
        return false;
    }

    /**
     * 包含所有字符的最短字符串
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s,String t) {
        HashMap<Character,Integer> charToCount = new HashMap<>();
        for (char ch : t.toCharArray()) {
            charToCount.put(ch,charToCount.getOrDefault(ch,0)+1);
        }
        int count = charToCount.size();
        int minLen = Integer.MAX_VALUE;
        int start = 0,end = 0,minStart = 0,minEnd = 0;
        while (end < s.length() || (count == 0 && end == s.length())) {
            if (count > 0) {
               char enChar = s.charAt(end);
               if (charToCount.containsKey(enChar)) {
                   charToCount.put(enChar,charToCount.get(enChar) - 1);
                   if (charToCount.get(enChar) == 0) {
                       count --;
                   }
                }
               end ++;
            } else {
                if (end - start < minLen) {
                    minLen = end - start;
                    minStart = start;
                    minEnd = end;
                }
                char startCh = s.charAt(start);
                if (charToCount.containsKey(startCh)) {
                    charToCount.put(startCh,charToCount.get(startCh) + 1);
                    if (charToCount.get(startCh) == 1) {
                        count ++;
                    }
                }
                start ++;
            }
        }
        return minLen<Integer.MAX_VALUE?s.substring(minStart,minEnd):"";
    }
    static class Peopal {
        char pos; // 内地还是外地
        char color; // 健康码颜色
        char yimiaojiezhong; // 疫苗接种情况
        char lastChekStat; // 上次检查结果
        int lastChekTime; // 最近一次检查时间

    }
    public int numOfSubarrays(int[] arr) {
        int sum = 0;
        int odd = 0; // 奇数
        int even = 1; // 偶数
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if(sum%2 == 0) {
                even ++;
                ans = (ans + odd) % 1000000007;// 奇数和的数组的数量
            } else {
                odd ++;
                ans = (ans + even) % 1000000007;
            }
        }
        return ans;
    }

    // 逆序数
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int N = sc.nextInt();
//        for (int i = N; i <= Integer.MAX_VALUE; i++) {
//            int ni = nixu(i);
//            if(Math.abs(i-ni) <= 200000 && Math.abs(i-ni) >= 100000) {
//                System.out.println(i);
//                return;
//            }
//        }
//        System.out.println("F");
//    }
//    private static int nixu(int n) {
//        // 100000,200000
//        int ans = 0;
//        while (n > 0) {
//            ans = ans*10 + n%10;
//            n /= 10;
//        }
//        return ans;
//    }

//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int N = sc.nextInt();
//        int M = sc.nextInt();
//        int[] egs = new int[N];
//        for (int i = 0; i < N; i++) {
//            egs[i] = sc.nextInt();
//        }
//        Arrays.sort(egs);
//        // 滑动窗口
//        float sum = 0;
//        float ans = 0;
//        int jicha = egs[M-1] - egs[0];
//        int r = 0;
//        int l = 0;
//        while (r < M) {
//            sum += egs[r];
//            r ++;
//        }
//        ans = sum;
//        while (r < N) {
//            sum -= egs[l];
//            sum += egs[r];
//            int curJicha = egs[r] - egs[l+1];
//            if(curJicha < jicha) {
//                ans = sum;
//                jicha = curJicha;
//            } else if (curJicha == jicha) {
//                ans = Math.max(ans,sum);
//            }
//            l ++;
//            r ++;
//        }
//        System.out.print(ans);
//    }
}