public static int[] getMilestoneDays(int[] revenues, int[] milestones) {
		int[] output = new int[milestones.length];
		Arrays.fill(output, -1);
		int sum = 0;
		for (int i = 0; i < revenues.length; i++) {
			revenues[i] += sum;
			sum = revenues[i];
		}
		for (int i = 0; i < milestones.length; i++) {
			int searchFor = milestones[i];
			int low = 0;
			int high = revenues.length - 1;
			int mid = 0;

			while (low <= high) {
				mid = (high + low) / 2;

				if (searchFor == revenues[mid]) {
					output[i] = mid;
					break;
				} else if (searchFor < revenues[mid] && (mid - 1 < revenues.length && searchFor > revenues[mid - 1])) {
					output[i] = mid - 1;
					break;
				} else if (searchFor < revenues[mid])
					high = mid - 1;
				else if (searchFor > revenues[mid] && (mid + 1 < revenues.length && searchFor < revenues[mid + 1])) {
					output[i] = mid + 1;
					break;
				} else if (searchFor > revenues[mid])
					low = mid + 1;

			}
		}
		for (int i = 0; i < output.length; i++)
			output[i]++;
		return output;
	}

	public static class Pair {
		int index;
		int value;

		public Pair(int index, int value) {
			super();
			this.index = index;
			this.value = value;
		}

		public int getIndex() {
			return index;
		}

		public void setIndex(int index) {
			this.index = index;
		}

		public int getValue() {
			return value;
		}

		public void setValue(int value) {
			this.value = value;
		}

	}

	public static int[] findPositions(int[] arr, int x) {
		Queue<Pair> q = new LinkedList<Pair>();
		for (int i = 0; i < arr.length; i++)
			q.add(new Pair(i + 1, arr[i]));
		ArrayList<Integer> removed = new ArrayList<Integer>();
		for (int i = x; i >= 1; i--) {
			int pops = x;
			PriorityQueue<Pair> maxHeap = new PriorityQueue<Pair>(new Comparator<Pair>() {
				@Override
				public int compare(Pair o1, Pair o2) {
					if (o1.getValue() == o2.getValue())
						return Integer.compare(o1.getIndex(), o2.getIndex());
					return -Integer.compare(o1.getValue(), o2.getValue());
				}
			});
			Queue<Pair> temp = new LinkedList<Pair>();
			while (pops != 0 && !q.isEmpty()) {
				Pair c = q.poll();
				maxHeap.add(c);
				temp.add(c);
				pops--;
			}
			Pair ToRemove = maxHeap.remove();
			int ToRemoveIndex = ToRemove.getIndex();
			removed.add(ToRemoveIndex);
			while (!temp.isEmpty()) {
				Pair a = temp.poll();
				if (a.getIndex() != ToRemoveIndex) {
					q.add((a.getValue() > 0) ? new Pair(a.getIndex(), a.getValue() - 1) : a);
				}
			}
		}
		int[] out = new int[removed.size()];
		for (int i = 0; i < out.length; i++)
			out[i] = removed.get(i);
		return out;
	}

 public static String caesarCipher(String input, int rotationFactor) {
    // Write your code here
StringBuilder sb = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) >= 'a' && input.charAt(i) <= 'z') {
                char newChar = (char) (input.charAt(i) + rotationFactor%26);
                sb.append((newChar >= 'a' && newChar <= 'z') ? newChar : (char) (newChar - 'z' - 1 + 'a'));
            } else if (input.charAt(i) >= 'A' && input.charAt(i) <= 'Z') {
                char newChar = (char) (input.charAt(i) + rotationFactor%26);
                sb.append((newChar >= 'A' && newChar <= 'Z') ? newChar : (char) (newChar - 'Z' - 1 + 'A'));
            } else
                sb.append(input.charAt(i));
        }
        return sb.toString();
    }

class Solution {
      public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> all = new ArrayList();
        
      List<Integer> first = new ArrayList<>();
      first.add(1);
      all.add(first);
      
      if(numRows >=2) {
    	  List<Integer> second = new ArrayList<>();
          second.add(1);
          second.add(1);
          all.add(second);  
      }
      for(int i = 2;i < numRows; i++) {
    	  List<Integer> row = new ArrayList<>();
    	  row.add(1);
    	  int start =0;
    	  for(int j = 1; start<all.get(i-1).size()-1; j++) {
    		  int a = all.get(i-1).get(start)+all.get(i-1).get(start+1);
    		  start++;
    		  row.add(a);
    	  }
    	  
    	 row.add(1);
    	 all.add(row); 
      }
        
        return all;
    }
}

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;
        ListNode current = head;
        while(current != null){
            len++;
            current = current.next;
        }
       int required = len - n;
        if(required == 0) return head.next;
        ListNode c = head;
        for(int i =0; i < len; i++){
            if(i == required-1) {
                c.next = c.next.next;
               
            }
             else c = c.next;
        }
        return head;
    }
}

class Solution {
    public boolean isPalindrome(String s) {

        StringBuilder sIgnoreBuffer = new StringBuilder();
        for (int i = 0; i < s.length(); i++){
            if((s.charAt(i)>='0' && s.charAt(i)<='9')||(s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'))
                sIgnoreBuffer.append(Character.toLowerCase(s.charAt(i)));
        }
    
        String sIgnore = sIgnoreBuffer.toString();
        int start = 0;
        int end = sIgnore.length() - 1;   
                                
        while(start < end){
            if(sIgnore.charAt(start) == sIgnore.charAt(end)){
                start++;
                end --;
            } else return false;
        }
       return true;
}}

class Solution {
    public void rotate(int[][] matrix) {
 
        for(int i = 0; i < matrix.length; i++){
            for (int j = i; j < matrix.length; j++){
                swap(i,j,j,i,matrix);

            }
        }
        
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix.length/2; j++){
            swap(i,j,i,matrix.length-1-j,matrix);

                }
        }
        
        
    }
    public void swap(int i, int j, int x, int y, int [][] matrix){
        int temp = matrix[i][j];
        matrix[i][j] = matrix[x][y];
        matrix[x][y] = temp;
    }
}

   class Solution {
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i < board.length; i++) { HashSet dataInRow = new HashSet();
for (int j = 0; j < board.length; j++) {
if (board[i][j] != '.')
if (dataInRow.contains(board[i][j]))
return false;
else
dataInRow.add(board[i][j]);
}
} for (int j = 0; j < board.length; j++) {
        HashSet<Character> dataInRow = new HashSet<Character>();
        for (int i = 0; i < board.length; i++) {
            if (board[i][j] != '.')
                if (dataInRow.contains(board[i][j]))
                    return false;
                else
                    dataInRow.add(board[i][j]);
        }
    }
    for (int i = 0; i < board.length; i = i + 3) {
        for (int j = 0; j < board.length; j = j + 3) {
            if (!checkValid(i, j, board))
                return false;
        }
    }

    return true;
}

private boolean checkValid(int a, int b, char[][] board) {
    HashSet<Character> dataInSquare = new HashSet<Character>();
    int aEnd = a + 3;
    int bEnd = b + 3;
    for (int i = a; i < aEnd; i++) {
        for (int j = b; j < bEnd; j++) {
            if (board[i][j] != '.')
                if (dataInSquare.contains(board[i][j]))
                    return false;
                else
                    dataInSquare.add(board[i][j]);
        }
    }
    return true;
}