class Solution {
    public int[] singleNumber(int[] nums) {
        int single1=0, single2=0;
        boolean found=false;
        Map<Integer, Integer> map = new HashMap<>();
        for(int num: nums){
            map.put(num, map.getOrDefault(num, 0) +1);
        }
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            if(entry.getValue()==1&&!found){
                single1=entry.getKey();
                found=true;
            }
            if(entry.getValue()==1&&found){
                single2=entry.getKey();
            }
        }
        return new int[]{single1, single2};
    }
}

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode head=list1;
        int diff=b-a;
        while(a-- > 1){
            list1=list1.next;
        }
        ListNode move=list1.next;
        list1.next=list2;
        while(diff-- >= 0){
            move=move.next;
        }
        while(list2.next!=null){
            list2=list2.next;
        }
        list2.next=move;
        
        return head;
    }
}

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int l=1, r=n, mid;
        while(l<=r){
            mid=l+(r-l)/2;
            if(guess(mid)==0) return mid;
            if(guess(mid)==1) l=mid+1;
            if(guess(mid)==-1) r=mid-1;
        }
        
        return l;
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        int i=nums.length-2, j=nums.length-1, temp;
        while(i>-1 && nums[i]>=nums[i+1])
            i--;
        if(i>=0){
            while(nums[i]>=nums[j])
            j--;
        
            temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
        int k=nums.length-1;
        i++;
        while(i<k){
            temp=nums[i];
            nums[i]=nums[k];
            nums[k]=temp;
            i++; k--;
        }
    }
}

class Solution {
    public int findFinalValue(int[] nums, int original) {
        for(int i=0; i<nums.length; i++){
            if(nums[i]==original){
                return findFinalValue(nums, 2*original);
            }
        }
        return original;
    }
}

class Solution {
    public static List<List<String>> displayTable(List<List<String>> orders) {
        int table; String food;
        Map<Integer, TreeMap<String, Integer>> map = new TreeMap<>();
        Set<String> set = new TreeSet<>();
        for (List<String> order : orders) {
            table = Integer.parseInt(order.get(1));food = order.get(2);
            set.add(food);
            TreeMap<String, Integer> foodMap;
            if (map.get(table) == null) foodMap = new TreeMap<>();
            else foodMap = map.get(table);
            foodMap.put(food, foodMap.getOrDefault(food, 0) +1);
            map.put(table, foodMap);
        }

        List<List<String>> list = new ArrayList<>();
        List<String> temp = new ArrayList<>(); temp.add("Table");
        for (String s: set)
            temp.add(s);
        list.add(temp);
        for (Map.Entry<Integer, TreeMap<String, Integer>> entry: map.entrySet()){
            temp = new ArrayList<>();
            temp.add(String.valueOf(entry.getKey()));
            for (String s : set)
                temp.add(String.valueOf(entry.getValue().getOrDefault(s, 0)));
            list.add(temp);
        }
        return list;
    }
}

public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> map = new HashMap<>(); String website, websites[]; int number; StringBuilder sb;
        for(String s: cpdomains){
            sb=new StringBuilder(); number=Integer.parseInt(s.split(" ")[0]);
            websites=s.split(" ")[1].split("\\.");
            for(int i=websites.length-1; i>0; i--){
                sb.insert(0, websites[i]);
                map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) +number);
                sb.insert(0, ".");
            } sb.insert(0, websites[0]);
            map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) +number);
        } List<String> list = new ArrayList<>();
        for(Map.Entry<String, Integer> entry: map.entrySet()){
            sb=new StringBuilder();
            sb.append(entry.getValue()).append(" ").append(entry.getKey());
            list.add(sb.toString());
        } return list;}

class Solution {
    public int percentageLetter(String s, char letter) {
        int count=0;
        for(char ch: s.toCharArray())
            if(ch==letter) count++;
        return count*100/s.length();
    }
}

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

class Solution {
    public boolean divisorGame(int n) {
        return n%2==0;
    }
}

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=nums1.length-1; i>=0; i--){
            if(m>0 && n>0){
                if(nums1[m-1]>nums2[n-1]){
                    nums1[i]=nums1[m-1];
                    m--;
                }else{
                    nums1[i]=nums2[n-1];
                    n--;
                }
            }
        }
        for(int i=n-1; i>=0; i--){
            nums1[i]=nums2[i];
        }
        
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
}

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length()==0) return true;
        int is=0, it=0;
        while(it<t.length()){
            if(s.charAt(is)==t.charAt(it)){
                is++;
                if(is==s.length()) return true;
            }
            it++;
        }
        return false;
    }
}

class Solution {
    public int minPartitions(String n) {
        for(int i=9; i>=0; i--){
            if(n.contains(""+i))
                return i;
        }
        return -1;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1=nums1.length, l2=nums2.length, l=l1+l2;
        int num[] = new int[l], i=0, j=0;
        for(; i<l1 || j<l2; ){
            if(i<l1 && j<l2){
                if(nums1[i]>nums2[j])
                    num[i+j]=nums2[j++];
                else
                    num[i+j]=nums1[i++];
            }else if(i<l1)
                num[i+j]=nums1[i++];
            else
                num[i+j]=nums2[j++];
        }
        return l%2==0 ? (num[l/2-1]+num[l/2])/2.0 : (double)num[l/2];
    }
}

class Solution {
    public String convert(String s, int n) {
        if(n==1) return s;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            for(int j=i; j<s.length(); ){
                sb.append(s.charAt(j));
                if(i!=0 && i!=n-1 && j<s.length()-(n-i-1)*2){
                    sb.append(s.charAt(j+(n-i-1)*2));
                }
                j=j+2*n-2;
            }
        }
        return sb.toString();
    }
}

class Solution {
    public int reverse(int x) {
        int res=0;
        boolean isPos=true;
        if(x<0){
            x=-x;
            isPos=false;
        }
        while(x>0){
            int last=x%10;
            x/=10;
            if(res>Integer.MAX_VALUE/10||res==Integer.MAX_VALUE/10 && last>=8) return 0;
            res=res*10+last;
            System.out.println(res);
        }
        return isPos ? res : -res;
    }
}