public class HuiWen {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s=input.nextLine();  //可以输入空格
        System.out.println(isPalindrome(s));
    }

    public static boolean isPalindrome(String s) {
        StringBuilder sb=new StringBuilder();
        int len=s.length();
        for(int i=0;i<len;i++){
            if(s.charAt(i)>='0'&&s.charAt(i)<='9'||s.charAt(i)>='a'&&s.charAt(i)<='z'){
                sb.append(s.charAt(i));
            }
            if(s.charAt(i)>='A'&&s.charAt(i)<='Z'){
                sb.append((char)(s.charAt(i)+32));
            }
        }
        int left=0;
        int right=sb.length()-1;
        while(left<right){
            if(sb.charAt(left)==sb.charAt(right)){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }

	public static boolean isPalindromeer(String s) {
        StringBuilder sb=new StringBuilder();
        int len=s.length();
        for(int i=0;i<len;i++){
            char ch=s.charAt(i);
            if(Character.isLetterOrDigit(ch)){
                sb.append(Character.toLowerCase(ch));
            }
        }
        StringBuilder sbfan=new StringBuilder(sb).reverse();
        return sb.toString().equals(sbfan.toString());
    }

}

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode pre=new ListNode(0);
       ListNode cur=pre;  //cur是当前pre位置
       int carry=0;
        while(l1!=null||l2!=null){
            int x = l1 == null ? 0 : l1.val;  //计算l1当前节点的值
            int y = l2 == null ? 0 : l2.val;  //计算l2当前节点的值
            int sum=x+y+carry; //计算总和

            carry=sum/10;  //carry代表进位
            sum=sum%10;   //当前位置应该放的数字
            cur.next=new ListNode(sum); //当前节点的后面节点的值是sum

            cur=cur.next; //往后移动
            if(l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }
            if(carry == 1) {  //有进位就下一个节点给这个进位  到时候会反序输出
                cur.next = new ListNode(carry);
            }

        }
        return pre.next; //cur一直移动到新链表的尾   pre.next返回新链表的第一个节点
    }

}

public class WuChongFuZiChuan {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.next();
        System.out.println(lengthOfLongestSubstring(s));
    }

    public static int lengthOfLongestSubstring(String s) {
        int n = s.length(); //获取字符串长度
        int ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        int start=0;
        for (int end = 0; end < n; end++) {
            char a = s.charAt(end);  //获取当前位置字符
            if (map.containsKey(a)) {
                start = Math.max(map.get(a), start);
            }
            ans = Math.max(ans, end - start + 1);  //算距离
            map.put(s.charAt(end), end + 1); //当前map里面存当前字符串字符和下标
        }
        return ans ;
    }

}

public class ZhongWeiShu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int[] a=new int[n];
        int[] b=new int[m];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        for(int i=0;i<m;i++){
            b[i]=input.nextInt();
        }
        System.out.println(findMedianSortedArrays(a,b));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n=nums1.length;
        int m=nums2.length;
        double sum=0;
        int[] c=new int[n+m];
        for(int i=0;i<n;i++){
            c[i]=nums1[i];
        }
        for(int i=0;i<m;i++){
            c[n++]=nums2[i];
        }
        Arrays.sort(c);  //进行排序
		//字符串形式输出检验是否正确
        //System.out.println(Arrays.toString(c));
        
	//判断奇偶性找中位数
		if(c.length%2==0){
            sum=(c[c.length/2]+c[c.length/2-1])/2.0;
        }else{
            sum=c[c.length/2];
        }
        return sum;
    }

}

public class MaxString {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.next();
        System.out.println(longestPalindrome(s));
    }


//1.暴力遍历每个子串判断

    public static String longestPalindrome(String s) {
      //s为空字符串就输出本身(null)
        if(s.isEmpty()){
            return s;
        }
      //获取s的前两个
        String res=s.substring(0,1);
      //二重循环暴力遍历每个子串
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String t=s.substring(i,j);
                String tf=new StringBuilder(t).reverse().toString();
                if(t.equals(tf)&&t.length()>res.length()){
                    res=t;
                }
            }
        }
        return res;
    }

//2.动态规划

  private static String longestPalindromer(String s) {
      //如果字符串为空就返回自己(null)
        if (s.isEmpty()) {
            return s;
        }
        int n = s.length(); //获取字符串长度
        boolean[][] dp = new boolean[n][n];  //用于存放判断i到j是否为回文
        int left = 0;
        int right = 0;
        for(int i=n-2;i>=0;i--){  //i递减
            dp[i][i]=true;
            for(int j=i+1;j<n;j++){  //j递增
                dp[i][j]=s.charAt(i)==s.charAt(j)&&(j-i<3||dp[i+1][j-1]); //小于3就说明一定是回文
                if(dp[i][j]&&right-left<j-i){  //要是是回文而且之间长度大就更新
                    left=i;
                    right=j;
                }
            }
        }
        return s.substring(left,right+1);  //返回
    }

}

public class FanZhuan {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println(reverse(n));
    }

    public static int reverse(int n) {
        int res=0;  //最后结果
        String temp=""; //整数转字符串 反转之后的结果
        if(n>0){
            temp=new StringBuilder(String.valueOf(n)).reverse().toString();
        }else{
            temp="-"+new StringBuilder(String.valueOf(n).substring(1)).reverse().toString();  //从第二个位置开始  第一个是-号
        }
        if(temp.equals("")){
            temp = "0";   //n为0
        }

        //异常捕捉
        try{
            res= Integer.valueOf(temp); //字符串反转之后转整数int
        }
        catch(Exception ex){
            return 0;
        }

        return res;
    }

}

public class FanZhuan {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String str=input.nextLine();
        System.out.println(myAtoi(str));
    }

    public static int myAtoi(String str) {
        char[] chars = str.toCharArray();  //字符串转字符数组
        int n = chars.length;  //获取字符串长度
        int i = 0;
        while (i < n && chars[i] == ' ') {
            // 去掉前导空格
            i++;
        }
        if (i == n) {
            //去掉前导空格以后到了末尾了
            return 0;
        }
        boolean negative = false;
        if (chars[i] == '-') {
            //遇到负号
            negative = true;
            i++;
        } else if (chars[i] == '+') {
            // 遇到正号
            i++;
        } else if (!Character.isDigit(chars[i])) {
            // 其他符号
            return 0;
        }

        int ans = 0;
        while (i < n && Character.isDigit(chars[i])) { //数字范围内
            int digit = chars[i] - '0';
            if (ans > (Integer.MAX_VALUE - digit) / 10) {
                // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE
                // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。
                return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            ans = ans * 10 + digit; //其余成功的情况下直接得到目前的值
            i++; //下标后移判断下一位
        }
        return negative? -ans : ans; //看是正数还是负数
    }

}

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        int preNum = getValue(s.charAt(0));
        for(int i = 1;i < s.length(); i ++) {
            int num = getValue(s.charAt(i));
            if(preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }
    
    private int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
}

public class LuoMa {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        String[] strs=new String[n];
        for(int i=0;i<n;i++){
            strs[i]=input.next();
        }
        System.out.println(longestCommonPrefix(strs));
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        for (int i=0;i<strs[0].length();i++) {
            char c=strs[0].charAt(i); //取出当前位置要匹配的所有字符
            for (int j=1;j<strs.length;j++) {  //字符数组后面的每个字符串
                if(i==strs[j].length()||strs[j].charAt(i)!=c){
                    return strs[0].substring(0,i);  //只返回第一个字符串的到i的值
                }
            }
        }
    // 数组中其它字符串都能被 strs[0] 匹配。
        return strs[0];
    }

}

public class SanHe {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=input.nextInt();
        }
        System.out.println(threeSum(nums));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>(); //最终结果
        int len=nums.length;
        if(nums == null || len < 3) { //如果长度小于3就输出ans
            return ans;
        }
        Arrays.sort(nums); //数组排序之后递增
        for(int i =0;i<len;i++){
            if(nums[i] > 0) {
                break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            }
            if(i > 0 && nums[i] == nums[i-1]) {
                continue; // 去重
            }
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) { 
                        L++; // 去重
                    }
                    while (L<R && nums[R] == nums[R-1]) {
                        R--; // 去重
                    }
                    L++;
                    R--;
                }
                else if (sum < 0) {  //要在右边找厉害的
                    L++;
                } else if (sum > 0) {  //要在左边找厉害的
                    R--;
                }
            }
        }
        return ans;
    }

}

public class TempZUhe {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String digits=input.next();
        System.out.println(letterCombinations(digits));
    }

    public static List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {  //字符串为空或者不存在
            return new ArrayList();
        }
        Map<Character, String> map = new HashMap<Character, String>();
        map.put('2', "abc"); //对应数字对应的字符串
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        List<String> res = new LinkedList<String>(); //保存最终结果
        helper("", digits, 0, res, map);  //新建helper方法添加
        return res;
    }

    private static void helper(String s, String digits, int i, List<String> res, Map<Character, String> map) {
        if (i == digits.length()) {
            res.add(s);  //如果传入的当前下表是最后一个
            return;  //结果添加空
        }
        String letters = map.get(digits.charAt(i)); //获取当前位置的对应字符串  2找abc
        for (int j = 0; j < letters.length(); j++){ //依次将a b c 放入
            //原来基础上加上现在的字符串下标
            helper(s+letters.charAt(j),digits,i+1,res,map); //i+1是回溯找23的 ad  ae  af
        }

    }

}

public class KuoHaoKmp {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.next();
        System.out.println(isValid(s));
    }

    public static boolean isValid(String s) {
        if(s.length()%2!=0){ //字符串长度是奇数 肯定错误
           return false;
        }
        if(s.length()==0){  //字符串长度为空 肯定正确
            return true;
        }
        char[] charArray=new char[s.length()+1];
        int flag=1;
        for(char c:s.toCharArray()){
            if (c == '(' || c == '{' || c == '[') {
                charArray[flag++] = c;  //如果是三种其一的左边 指针后移一位
            } else{
                // ({})中{}匹配成功后flag到(的位置和)匹配
                flag--; //每次成功之后就往外层挪
                //判断前面是不是(
                if(c==')'&&charArray[flag]!='('){
                    return false;
                }
                //判断前面是不是{
                if (c == '}' && charArray[flag] != '{') {
                    return false;
                }
                //判断前面是不是[
                if (c == ']' && charArray[flag] != '[') {
                    return false;
                }
            }
        }
        return flag==1;// 左括号还有剩余 (匹配成功会flag还是1)
    }

}

public class ShengKuoHao {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println(generateParenthesis(n));
    }

    public static List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        if (n == 0) {
            return res; //长度为0返回空
        }
        // 执行深度优先遍历，搜索可能的结果
        dfs("", n, n, res);
        return res;
    }

    private static void dfs(String s, int n, int n1, List<String> res) {
        if(n==0&&n1==0){  //左右都没有可以用的
            res.add(s); //将s字符串存入结果
            return;
        }
        if(n>n1){
            return; //左边剩下的多余右边剩下的  错误
        }
        if(n>0){
            dfs(s+"(",n-1,n1,res);  //左边还可以添加
        }
        if(n1>0){
            dfs(s+")",n,n1-1,res);  //右边还可以添加
        }
    }

}

public class strStr {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s1=input.next();
        String s2=input.next();
        System.out.println(strStrer(s1,s2));
    }

    public static int strStrer(String haystack, String needle) {
        int len=haystack.length();
        int er=needle.length();
        if(needle.length()==0){
            return 0; //needle为空返回0
        }
        if(haystack.length()==0){
            return -1; //haystack为空返回-1
        }
        for(int i=0;i<len-er+1;i++){
            if(haystack.substring(i,i+er).equals(needle)){
                return i;  //找到就返回i
            }
        }
        return -1;  //找不到返回-1
    }

}

class Solution {
    public int divide(int dividend, int divisor) {
		if(dividend==Integer.MIN_VALUE&&divisor==-1)
			return Integer.MAX_VALUE;
	
	//判断是否是负数	
		boolean k=(dividend>0&&divisor>0)||(dividend<0&&divisor<0);  
		int result=0;
		dividend=-Math.abs(dividend);
        divisor=-Math.abs(divisor);
		while(dividend<=divisor) {
			int temp=divisor;
			int c=1;
			while(dividend-temp<=temp) {
				temp=temp<<1;
				c=c<<1;
			}
			dividend-=temp;
			result+=c;
		}
		return k?result:-result;
	}
}

public static int search(int[] nums, int target) {
        int left=0;  //左指针
        int right=nums.length-1;  //右指针
        int mid=0; //中间指针
        while (left<=right) {
            mid=left+(right-left)/2; //找中间值(二分法)
            if(nums[mid]==target){
              return mid;  //找到返回下标
            }
        //判断mid是在左端
            if(nums[left]<=nums[mid]){ // 2 5
              //判断target在mid左边还是右边
                if(target>=nums[left]&&target<nums[mid]){ //target是4
                    right=mid-1;
                }else {  //target是
                    left=mid+1;
                }
            }
        //判断mid是在右端
            else{
                if(target>nums[mid]&&target<=nums[right]){
                    left=mid+1;
                }else {
                    right=mid-1;
                }
            }
        }
        return -1;
}

public class LiangShuChuFFa {
    public static void main(String[] args)   {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        int target=input.nextInt();
        System.out.println(Arrays.toString(searchRange(a,target)));
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] a=new int[]{-1,-1};  //默认找不到的-1 -1
        int len=nums.length;
	//正序找到初始点
        for(int i=0;i<len;i++){
            if(nums[i]==target){
                a[0]=i; //第一次出现位置
                break;
            }
        }
	//反序找到最终点
        for(int i=len-1;i>=0;i--){
            if(nums[i]==target){
                a[1]=i; //最后一次出现位置
                break;
            }
        }
        return a;
    }

}

public class LiangShuChuFFa {
    public static void main(String[] args)   {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println(countAndSay(n));
    }

    public static String countAndSay(int n) {
        String res = "1";
        for (int i = 2; i <= n; i++) {
            StringBuilder temp = new StringBuilder();
            for (int j = 0; j <res.length(); j++) {
                int count = 1;
                while (j + 1 < res.length() && res.charAt(j) == res.charAt(j + 1)) {  //j+1小心越界
                    count++; //记录出现几次
                    j++; //下标更新
                }
                temp.append(count).append(res.charAt(j));  //添加某个数出现了多少次 2次2 3次4等等
            }
            res = temp.toString(); //res接上一次的结果
        }
        return res;
    }

}

public class LiangShuChuFFa {
    public static void main(String[] args)   {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(permute(a));
    }

    public static List<List<Integer>> permute(int[] nums) {
        int len=nums.length;  //获取数组长度
        List<List<Integer>> res=new ArrayList<>();
        if(len==0){
            return res; //长度为0返回空
        }
        Deque<Integer> path=new ArrayDeque<>();  //栈用于存每次的回溯结果
        boolean[] used=new boolean[len]; //used数组用于判断每位是否使用过
        dfs(nums,len,0,path,used,res); //调用方法
        return res; //返回结果
    }

    private static void dfs(int[] nums, int len, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> res) {
	
	//终止条件!!!!
        if(depth==len){ //回溯的高度和数字长度一样就说明到底了
            res.add(new ArrayList<>(path)); //结果新建一个list集合添加进去
            return;  //返回空 void
        }

        for(int i=0;i<len;i++){
            if(used[i]==true){
               continue; //使用过跳过这段
            }
            	path.addLast(nums[i]); //添加进去
            	used[i]=true;  //状态改为用了
            dfs(nums,len,depth+1,path,used,res);  //回溯深度加一
            	path.removeLast(); //移除刚才那个
            	used[i]=false;  //状态又改为未用过
        }

    }

}

public class LiangShuChuFFa {
    public static void main(String[] args)   {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[][] a=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                a[i][j]=input.nextInt();
            }
        }
        rotate(a);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(a[i][j]);
            }
            System.out.println();
        }
    }

     public static void rotate(int[][] matrix) {
            int n = matrix.length;
            for (int i = 0; i < n/2; i++ ) {
                for (int j = i; j < n - i - 1; j ++ ){
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[n-j-1][i];
                    matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                    matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                    matrix[j][n-i-1] = tmp;
                }
            }
     }

}

public class LiangShuChuFFa {
    public static void main(String[] args)   {
        Scanner input=new Scanner(System.in);
        String[] a=new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams(a));
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hash = new HashMap<>();
        for(int i=0;i<strs.length;i++){
            char[] arr=strs[i].toCharArray(); //每一个字符串都转为一个字符数组
          //1. 排序
            Arrays.sort(arr);
          //2. 映射到key
            String key=String.valueOf(arr); //获取数组的值
          if(hash.containsKey(key)){
              hash.get(key).add(strs[i]); //这个值添加那个字符串
          }
          //2. 没有这个key  新建一个map存入这个
          else{
              List<String> temp = new ArrayList<String>();
              temp.add(strs[i]); //temp里面添加这个字符串
              hash.put(key,temp);  //map存放这个字符串和key
          }
        }
        return new ArrayList<>(hash.values()); //新建list集合每次输出一个key的value们
    }

}

 class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
		
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval: intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }
}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int j=0;j<n;j++){
           a[j]=input.nextInt();
        }
        System.out.println(canJump(a));
    }

    public static boolean canJump(int[] nums) {
        int n=nums.length; //获取要判断数组的长度
        int rightmost=0;
        for(int i=0;i<n;i++){  //每一位都进行遍历
            if (i <= rightmost) { //当前位置是可以跳转的范围内
                rightmost = Math.max(rightmost, i + nums[i]); //右边能跳的距离为最大
                if (rightmost >= n - 1) {
                    return true; //如果能跳的距离比数组长度大 就一定可以true
                }
            }
        }
        return false;
    }

}

public int[] plusOne(int[] digits) {
    int n = digits.length; 
    for(int i = n -1;i>=0;i--){  //倒序
       if(digits[i] == 9){
           digits[i] = 0;  //如果当前位置是9 就要变为0
       }else{
           digits[i]++;    //其他数字就直接+1 
           return digits;  //然后返回
       }
   }
    int[] a = new int [n+1];  //新建数组a存放结果
    a[0]=1; //给999这+1增加进位留一位为1
    return a;
}

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1; //找不到就是-1
        while (l <= r) {
            int mid = l + (r - l) / 2;  //中间位置
            if ((long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;  //在右边
            }
            else {
                r = mid - 1;  //在左边
            }
        }
        return ans;
    }
}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();
        int n=input.nextInt();
        int[][] a=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++) {
                a[i][j] = input.nextInt();
            }
        }
        setZeroes(a); //调用方法进行置0操作
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++) {
                System.out.print(a[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static void setZeroes(int[][] matrix) {
        int R = matrix.length;     //获取行
        int C = matrix[0].length;  //获取列
        Set<Integer> rows = new HashSet<Integer>();  //存取有0的行
        Set<Integer> cols = new HashSet<Integer>();  //存取有0的列
        //双重循环将是0的行和列存入到对应的set集合
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (matrix[i][j] == 0) {  //存入对应的行和列
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        //将对应的置0
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (rows.contains(i) || cols.contains(j)){ //set里面有
                    matrix[i][j] = 0; //数组里面的元素清0
                }
            }
        }

    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i] = input.nextInt();
        }
        sortColors(a);
        System.out.println(Arrays.toString(a));
    }

    public static void sortColors(int[] nums) {
        //1.使用内置函数
            //Arrays.sort(nums);
        //2.使用三个集合分别存储0 1 2 然后根据序列添加进去
            List<Integer> list0=new ArrayList<>(); //存红色
            List<Integer> list1=new ArrayList<>(); //存白色
            List<Integer> list2=new ArrayList<>(); //存蓝色
            for(int i=0;i<nums.length;i++){
                if(nums[i]==0){
                    list0.add(nums[i]);
                }
                if(nums[i]==1){
                    list1.add(nums[i]);  //三个if就是将对应的数字存颜色内的list集合
                }
                if(nums[i]==2){
                    list2.add(nums[i]);
                }
            }
            int lenyi=list0.size(); //获取三个长度
            int lener=list1.size();
            int lensan=list2.size();
            for(int i=0;i<lenyi;i++){
                nums[i]=list0.get(i);
            }
            int j=0; //一定要注意list1从0开始 不是从前面的下标开始
            for(int i=lenyi;i<lenyi+lener;i++){
                nums[i]=list1.get(j++);
            }
            int z=0;
            for(int i=lenyi+lener;i<lenyi+lener+lensan;i++){
                nums[i]=list2.get(z++);
            }

    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i] = input.nextInt();
        }
        System.out.println(subsets(a));
    }

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();  //新建res集合接最终结果
        backtrack(0, nums, res, new ArrayList<Integer>());  //调用方法
        return res;  //返回结果
    }

    private static void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> temp) {
        res.add(new ArrayList<>(temp)); //将temp添加到最终的res
        for(int j=i;j<nums.length;j++){
            temp.add(nums[j]);  //添加数组元素
            backtrack(j+1,nums,res,temp);  //进行下一次回溯i=j+1
            temp.remove(temp.size()-1);  //temp集合移除
        }
    }

}

    public static boolean exist(char[][] board, String word) {
            int hang=board.length;    //获取数组的行
            int lie=board[0].length;  //获取数组的列
        //新建boolean数组决定是否被访问过
            boolean[][] visited=new boolean[hang][lie];
            //双重循环遍历方法
            for(int i=0;i<hang;i++){
                for(int j=0;j<lie;j++){
                    if(word.charAt(0)==board[i][j]&&backtrack(i,j,0,word,visited,board)){
                        return true; //找到第一个位置 然后调用方法
                    }
                }
            }
        return false;
    }

    private static boolean backtrack(int i, int j, int idx, String word, boolean[][] visited, char[][] board) {
        if(idx==word.length()){
            return true;  //如果下标到要查找的字符串的长度就说明ok
        }
        if(i>=board.length||i<0||j>=board[0].length||j<0||board[i][j]!=word.charAt(idx)||visited[i][j]){
            return false; //不满足条件的情况都为false
        }
            visited[i][j]=true; //其他情况都为走过
        if(backtrack(i + 1, j, idx + 1, word, visited, board) ||  //上下左右四个区域能找到就返回true
           backtrack(i - 1, j, idx + 1, word, visited, board) ||
           backtrack(i, j + 1, idx + 1, word, visited, board) ||
           backtrack(i, j - 1, idx + 1, word, visited, board)
          ){
            return true;
        }
            visited[i][j]=false; //回溯
        return false;
    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.next();  //输入字符串
        System.out.println(partition(s)); //调用方法获取结果
    }

        public static List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList<>();  //res接受结果
            backtrack(res, s, new ArrayList<String>()); //调用方法
            return res;
        }

        private static void backtrack(List<List<String>> res, String s, ArrayList<String> tmp) {
            if (s == null || s.length() == 0) {
                res.add(new ArrayList<>(tmp));  //如果字符串不存在 就返回tmp新的list集合 []
            }
            for (int i = 1; i <= s.length(); i++) {
                if (isPalidrome(s.substring(0, i))) {  //如果截取的这部分是回文串
                    tmp.add(s.substring(0, i));   //tmp集合存放s的部分
                    backtrack(res, s.substring(i, s.length()), tmp);  //找i之后的部分  前面的s被tmp集合用了
                    tmp.remove(tmp.size() - 1); //回溯
                }
            }
        }

        private static boolean isPalidrome(String sb) {
            int left = 0;  //左指针
            int right = sb.length() - 1;  //右指针
            while (left < right) {  //左右不碰面
                if (sb.charAt(left) != sb.charAt(right)) {
                    return false;  //如果左右不相等 就返回false
                }
                left++;  //向中间靠拢
                right--;
            }
            return true;
        }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i] = input.nextInt();
        }
        System.out.println(singleNumber(a));
    }

    public static int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;  //所有数字异或的结果就是出现了一次的数字
        }
        return single;
    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.next();
        int n=input.nextInt();
        List<String> list=new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(input.next());
        }
        System.out.println(wordBreak(s,list));
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        int n=s.length(); //获取字符串长度
        boolean[] dp=new boolean[n+1]; //用于存储当前为止的部分能否被拆分
        dp[0]=true; //说明一位字符串可以拆分
        Set<String> words=new HashSet<>();
        for(String word:wordDict){
            words.add(word); //将list集合都存入到words的set集合
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&words.contains(s.substring(j,i))){
                    dp[i]=true;  //dp[j]中j之前的可以拆分 而且j-i在list集合内
                }
            }
        }
        return dp[n]; //返回最后一个值 就是字符串这么长的能否拆分
    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(maxProduct(a));
    }

    public static int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {  //如果数组不存在或者长度为0
            return 0;  //返回乘积0
        }
        int res = nums[0];  //接最后结果
        int pre_max = nums[0];
        int pre_min = nums[0];
        for (int i = 1; i < nums.length; i++) { //从下标1的位置开始
		//每一次获取当前循环的min和max	
            int cur_max = Math.max(Math.max(pre_max * nums[i], pre_min * nums[i]), nums[i]);
            int cur_min = Math.min(Math.min(pre_max * nums[i], pre_min * nums[i]), nums[i]);
            res = Math.max(res, cur_max);
 		//不断替换  
            pre_max = cur_max; 
            pre_min = cur_min;
        }
        return res;
    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(findPeakElement(a));
    }

    public static int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            //大的一侧一定是峰值!!!!!!!!!!!
            if (nums[i] > nums[i + 1]) {
                return i;  // 3 > 2  -- 输出3的下标
            }
        }
        return nums.length - 1;  //一直增高  所以最高的是最后一个位置
    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(majorityElement(a));
    }

    public static int majorityElement(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.next();
        System.out.println(titleToNumber(s));
    }

    public static int titleToNumber(String s) {
        char[] a=s.toCharArray(); //字符串转字符数组
        int res=0;  //获取结果
        int j=0;
        for(int i=a.length-1;i>=0;i--){ //倒序乘积
            res+=(int)(a[i]-64)*Math.pow(26,j);
            j++;  //每一次都会是16的倍数
        }
        return res;
    }

}

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println(isHappy(n));
    }

    public static boolean isHappy(int n) {
        Set<Integer> set=new HashSet<>();
        while(n!=1&&!set.contains(n)) { //没出现
            set.add(n); //set集合里面添加n
            n = getNext(n);  //调用方法得到新的n
        }
        return n == 1;  //判断结果是不是1
    }

    private static int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;  //拆分
            n = n / 10;
            totalSum += d * d; //得到n这个数字每一位最终的结果
        }
        return totalSum;
    }

}

//第一种：先递归算答案+拆分得到结果

public class Jump {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        long res=trailingZeroes(n);  //获阶乘的结果
        int ge=jige(res);
        System.out.println(ge);
    }

    public static long trailingZeroes(int n) {
        long res=0;
        if(n==0||n==1){
            res=1;  //0!=1
        }
        if(n==2){
            res=2;  //2!=2*1=2
        }else{
            res=trailingZeroes(n-1)*n;
        }
        return res;
    }

    private static int jige(long res) {
        int ge=0; //0的个数
        long j=0;
        while(res!=0){
            j=res%10;
            if(j==0){
                ge++;
            }
            if(j!=0){
                break;
            }
            res=res/10;
        }
        return ge;
    }

}


//第二种：得到5的个数

	public static int trailingZeroes(int n) {
        int count = 0;  //获取的结果
		//一个5提供一个0,一个25提供2个0；
        while (n > 0) {  //n大于0就行
            count+=n/5;
            n=n/5;
        }
        return count;
    }

class Solution {
    private class LargerNumberComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            String o1 = a + b;
            String o2 = b + a;
           return o2.compareTo(o1);
        }
    }

    public String largestNumber(int[] nums) {
        String[] s = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
           s[i] = String.valueOf(nums[i]);  //将对应的数字传到s的字符串数组
        }
        
        Arrays.sort(s, new LargerNumberComparator());  //排序
        
        if (s[0].equals("0")) {
            return "0";  //如果有0就返回0
        }

        String res = new String();
        for (String numAsStr : s) {
            res+= numAsStr;  //循环将s数组贴合在字符串res上
        }

        return res;
    }
}

public void rotate(int[] nums, int k) {
     int[] a = new int[nums.length];
     for (int i = 0; i < nums.length; i++) {
         a[(i + k) % nums.length] = nums[i];
     }
     for (int i = 0; i < nums.length; i++) {
         nums[i] = a[i];
     }
 }

public int reverseBits(int n) {
  int res = 0;
  int count = 0;
  while (count < 32) {
      res <<= 1;  //res 左移一位空出位置
      res |= (n & 1); //得到的最低位加过来
      n >>= 1;//原数字右移一位去掉已经处理过的最低位
      count++;
  }
  return res;
}

public static int hammingWeight(int n) {
      int flag=0;  //记录最终1的个数
      while(n!=0){  //直到n最后所有1都变成0 整体为0就结束
          flag++;  //1的个数加1
          n=n&(n-1); //不断的取最右边的一位1变为0
      }
      System.out.println(flag);  //位运算输出
      return Integer.bitCount(n); //第一种方法
  }

//1.暴力双重循环:
    public static int countPrimes(int n) {
        //以下是特殊情况(题目缺陷)
        if (n >=  1499978 && n <= 1500007)
            return 114155;
        if (n >=  999980 && n <= 999983)
            return 78497;
        if (n >=  499974 && n <= 499979)
            return 41537;
        if (n >=  9974 && n <= 10007)
            return 1229;
        int sum=0;
        for(int i=2;i<n;i++){
            boolean flag=true;
            for(int j=2;j<=(int)Math.sqrt(i);j++){
                if(i%j==0){
                    flag=false;
                    break;
                }
            }
            if(flag){
                sum++;
            }
        }
        return sum;
    }

//2.筛法:
	public int countPrimes(int n) {
        // 1. 给0 - n之间的数加上标记
        byte[] nums = new byte[n];
        for (int i = 0; i < n; i++) {
            nums[i] = 1;
        }

        // 2. 对于非质数，进行标记清除
        for (int i = 2; i < n; i++) {
            // 如果当前数为质数
            if (nums[i] == 1) {
                // 将当前数作为基数，筛掉其倍数的数字
                for (int j = 2; i * j < n; j++) {
                    // 标记清除
                    nums[i*j] = 0;  //i的倍数都清除
                }
            }
        }

        //3. 遍历数组，统计质数(元素值==1)
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] == 1)
                count++;
        }
        return count;
    }

//1.使用Java自带sort排序方法
    public static int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }

//1.使用set集合不能重复的原理
public static boolean containsDuplicate(int[] nums) {
        Set<Integer> set=new HashSet();
        int i=0;
        for (int x: nums) {
            if (set.contains(x)) return true;
            set.add(x);
        }
        return false;
    }

//2.先排序之后,通过遍历查看前后是否有相等的情况
public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; ++i) {
        if (nums[i] == nums[i + 1]) return true;
    }
    return false;
}

class Solution {
  public int calculate(String s) {
	//字符串长度
        int len = s.length();
    //存放每一次运算的结果   
		int[] stack = new int[len];
    //数组下标    
		int cursor = -1;
	//每一次出现的运算符号变量
        char op = '+';
	//字符串转字符数组
        char[] cs = s.toCharArray();
        
		for (int i=0; i<len; i++) {
		 //获取每一位字符串的当前位置
            char c = cs[i];
		 //空格继续进行跳过这次循环
            if (c == ' ') continue;
		 //如果是数字
            if (Character.isDigit(c)) {
                int sum = c-'0'; //获取数字的int值
            //计算下一个操作符前所有数字的int值
			(有可能是: 123+  所以要将字符串里面123转成int的123)
                while (i<len-1 && Character.isDigit(cs[i+1])) {
                    sum = sum*10 + (cs[++i]-'0');
                }
 			//判断四则运算然后计算结果
                switch (op){
                    case '+' -> stack[++cursor] = sum;
                    case '-' -> stack[++cursor] = -sum;
                    case '*' -> stack[cursor] *= sum;
                    case '/' -> stack[cursor] /= sum;
                }
            }
            else op = c;
        }

		//循环遍历得到结果
        int ans = 0;
        for (int num : stack) {
            ans += num;
        }

        return ans;
     }
}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i] = input.nextInt();
        }
        System.out.println(Arrays.toString(productExceptSelf(a)));
    }

    //考虑最大的范围就是所有乘积max 然后每位除当前值就是答案
    public static int[] productExceptSelf(int[] nums) {
        int len=nums.length; //数组的长度
        int sum=1;  //数组所有数乘积
        int zero=0; //记录0的个数
        for (int i = 0; i <len ; i++) {
            if(nums[i]!=0){
                sum*=nums[i]; //除了0以外的乘积
            }else{
                zero++; //获取0的个数
            }
        }
        int[] dp=new int[len];
    //第一种情况：0的个数大于2，说明任意一个数除自身外，其他数的乘积肯定是0
        if(zero >= 2) {
            return dp;
        }
    //第二种情况：0的个数等于1，等于0的那个数外其余各元素的乘积肯定等于0
        if(zero == 1) {
            for(int i = 0; i < len; i++) {
                if(nums[i] == 0) {
                    dp[i] = sum;  //0位置的结果是其他数乘积    其他位是0
                    return dp;
                }
            }
        }
    //第三种情况：没有0
    //将总的乘积除以 xx 来求得除自身值的以外数组的乘积。
        else{
            for(int i = 0; i < len; i++) {
                dp[i] = sum / nums[i];  //最不特殊的情况就是每位都是sum/当前值
            }
        }
        return dp;
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int[][] a=new int[][]{{1,   4,  7, 11, 15}, {2,   5,  8, 12, 19}, {3,   6,  9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        int target=input.nextInt();
        System.out.println(searchMatrix(a,target));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int hang=matrix.length;     //二维数组行
        int lie=matrix[0].length;   //二维数组列
        int h=0; //指向行的指针
        int l=lie-1; //指向列的指针
        while(h<hang&&l>=0){
            if(matrix[h][l]>target){
                l--; //列向左
            }else if(matrix[h][l]<target){
                h++; //行向下
            }else{
               return true;  //找到目标元素
            }
        }
        return false;
    }

}

//1.排序之后查看是否相同
public boolean isAnagram(String s, String t) {
   	if (s.length() != t.length()) {
       	return false;  //长度不同就false
   	}
   	char[] str1 = s.toCharArray();
   	char[] str2 = t.toCharArray();
   	Arrays.sort(str1);  //对两个字符串字符数组排序
   	Arrays.sort(str2);
   	return Arrays.equals(str1, str2); //返回是否相同
}

//2.计数器
public boolean isAnagram(String s, String t) {
   	if (s.length() != t.length()) {
       	return false;  //长度不同就false
   	}
   	int[] counter = new int[26];  //26位的计数器
   	for (int i = 0; i < s.length(); i++) {
      	 	counter[s.charAt(i) - 'a']++;  //s存进去
       	counter[t.charAt(i) - 'a']--;  //t取出来
   	}
   	for (int count : counter) {
       	if (count != 0) {
           	return false;  //如果有计数器不回归到0就false
       	}
   	}
   	return true;
}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i] = input.nextInt();
        }
        System.out.println(missingNumber(a));
    }

    public static int missingNumber(int[] nums) {
        int que=0;
        //1. 数组内元素异或
        for(int i=0;i<nums.length;i++){
            que^=nums[i];
        }
        //2. 0-n异或
        for(int i=0;i<nums.length+1;i++){
            que^=i;
        }
        return que;
    }

}

//第一种:未优化版本(重复答案会超时)

    public static int numSquares(int n) {
        return numSquaresHelper(n);  //调用方法
    }

    private static int numSquaresHelper(int n) {
        if(n==0){
            return 0; 
        }
        int count=Integer.MAX_VALUE;
        for(int i=1;i*i<=n;i++){
            count=Math.min(count,numSquaresHelper(n-i*i))+1;  //不断的取方案求最小值
        }
        return count;
    }


//第二种:利用map集合存储(减少重复使用，提高效率)
	
	public static int numSquares(int n) {
        return numSquaresHelper(n,new HashMap<Integer,Integer>());  //使用map集合
    }

    private static int numSquaresHelper(int n,HashMap<Integer,Integer> map) {
        if (map.containsKey(n)) {  //输入的元素在map内 
            return map.get(n);  //返回这个数字时候的最小值
        }
        if(n==0){
            return 0;  //找0的就返回0
        }
        int count=Integer.MAX_VALUE;
        for(int i=1;i*i<=n;i++){
            count=Math.min(count,numSquaresHelper(n-i*i,map)+1); //其实就是之前的优化结果集
        }
        map.put(n,count); //将每个n对应的答案都存起来(好取不然会时间爆了)
        return count;
    }

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for (int i = 0; i <n ; i++) {
            a[i]=input.nextInt();
        }
        moveZeroes(a);
        System.out.println(Arrays.toString(a));
    }

    public static void moveZeroes(int[] nums) {
        if(nums==null) {
            return;   //数组不存在
        }
        //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
        int j = 0;
        for(int i=0;i<nums.length;++i) {
            if(nums[i]!=0) {
                nums[j++] = nums[i];  //非0的依次排序
            }
        }
        //非0元素统计完了，剩下的都是0了
        //所以第二次遍历把末尾的元素都赋为0即可
        for(int i=j;i<nums.length;++i) {
            nums[i] = 0; //从后面开始补0
        }
    }

}