class Solution {
    public boolean isPowerOfThree(int n) {
        return n>0 && 1162261467%n==0?true:false;
    }
}

class Solution {
    public boolean isPowerOfThree(int n) {
    	if (n<=0) return false;
    	double power = Math.log10(n)/Math.log10(3);
    	return power==Math.ceil(power)?true:false;        
    }
}

class Solution {
	public int[] nextVector(String P) {
		int[] arr = new int[P.length()];
		arr[0] = 0;
		int k = 0;
		for (int i = 1; i < P.length(); i++) {
			k = arr[i - 1];

			while (k > 0 && P.charAt(i) != P.charAt(k)) {
				k = arr[k - 1];
			}

			if (P.charAt(i) == P.charAt(k))
				arr[i] = k + 1;
			else
				arr[i] = 0;
		}
		return arr;
	}

	public int findPat_KMP(String S, String P, int[] N, int startIndex) {
		int lastIndex = S.length() - P.length();
		if (lastIndex < startIndex)
			return -1;
		int i = startIndex, j = 0;
		for (; i < S.length(); i++) {
			while (P.charAt(j) != S.charAt(i) && j > 0)
				j = N[j - 1];
			if (S.charAt(i) == P.charAt(j))
				j++;
			if (j == P.length())
				return i - j + 1;
		}
		return -1;
	}    

    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
    	int[] arr = nextVector(needle);
    	if (needle.isEmpty()) return 0;
        return findPat_KMP(haystack,needle,arr,0);        
    }
}

class Solution {
    public int strStr(String haystack, String needle) {
    	if (needle.isEmpty()) return 0;
        return haystack.indexOf(needle);        
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
    	if (nums.length<2) return nums.length;
    	int x=0,y=1;
    	while (y<nums.length) {
    		if (nums[x]==nums[y]) {
    			y+=1;
    		}
    		else {
    			x+=1;
    			nums[x]=nums[y];
    			y+=1;
    		}
    	}
        return x+1;        
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
    	if (nums.length==0) return 0;
    	int j=0;
    	for(int i=0;i<nums.length;i++) {
    		if (nums[i]!=nums[j])
    			nums[++j]=nums[i];
    	}
    	return ++j;       
    }
}

class Solution {
    public int romanToInt(String s) {
    	if (s==null || s.isEmpty()) return -1;
    	Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);    	
    	char[] arr = s.toCharArray();
    	int len = arr.length;
    	int sum = map.get(arr[len-1]);
    	for(int i=0;i<len-1;i++) {
    		if (map.get(arr[i])>=map.get(arr[i+1])) {
    			sum += map.get(arr[i]);
    		}
    		else {
    			sum -= map.get(arr[i]);
    		}
    	}
        return sum;        
    }
}

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode head = new ListNode(0);
		ListNode p = head;

		ListNode p1 = l1;
		ListNode p2 = l2;
		while (p1 != null && p2 != null) {
			if (p1.val < p2.val) {
				p.next = p1;
				p1 = p1.next;
			} else {
				p.next = p2;
				p2 = p2.next;
			}
			p = p.next;
		}

		if (p1 != null) {
			p.next = p1;
		}

		if (p2 != null) {
			p.next = p2;
		}

		return head.next;        
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	if (l1==null) return l2;
    	if (l2==null) return l1;
    	if (l1.val<l2.val) {
    		l1.next = mergeTwoLists(l1.next,l2);
    		return l1;
    	}
    	else {
    		l2.next = mergeTwoLists(l1,l2.next);
    		return l2;
    	}        
    }
}

class Solution {
    public boolean validUtf8(int[] data) {
    	int count=0;
    	for(int k : data) {
    		if (count==0) {
    			if ((k>>5)==0b110) count=1;
    			else if ((k>>4)==0b1110) count=2;
    			else if ((k>>3)==0b11110) count=3;
    			else if ((k>>7)==1) return false;
    		}
    		else {
    			if ((k>>6)!=0b10) return false;
    			count--;
    		}
    	}
    	return count==0;        
    }
}

import java.util.Random;

class Solution {
	private int[] shuffleArr;
	private int[] originalArr;    

    public Solution(int[] nums) {
    	originalArr = nums.clone();
    	shuffleArr = nums.clone();       
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
    	Random random = new Random();
    	int temp = 0;
    	int randomPosition = 0;
    	final int N = shuffleArr.length;
    	for(int i=shuffleArr.length-1;i>0;i--) {
    		randomPosition = random.nextInt(N);
    		temp = shuffleArr[i];
    		shuffleArr[i] = shuffleArr[randomPosition];
    		shuffleArr[randomPosition] = temp;
    	}
        return shuffleArr;
    }
}

class Solution {
    private int[] shuffleArr;
    private int[] originalArr;
    
    public Solution(int[] nums) {
        originalArr = nums.clone();
        shuffleArr = nums.clone();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        final int N = shuffleArr.length;
        int swap;
        for (int i = 0; i < N; i++) {
            int r = (int) (Math.random() * (i + 1));
            swap = shuffleArr[r];
            shuffleArr[r] = shuffleArr[i];
            shuffleArr[i] = swap;
        }
        return shuffleArr;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
	private Integer[] shuffleArr;
	private int[] originalArr;    

    public Solution(int[] nums) {
    	shuffleArr = new Integer[nums.length];
    	for(int i=0;i<nums.length;i++)
    		shuffleArr[i] = nums[i];
    	originalArr = nums.clone();       
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
    	List<Integer> list = Arrays.asList(shuffleArr);
    	Collections.shuffle(list);
    	Integer[] a = new Integer[shuffleArr.length];
    	list.toArray(a);
    	int[] r = new int[a.length];
    	for(int i=0;i<a.length;i++)
    		r[i] = a[i];
        return r;        
    }
}

class MyHashMap {
    static final int N = 1000000;
	private int[] arr;

    /** Initialize your data structure here. */
    public MyHashMap() {
        arr = new int[N];
        Arrays.fill(arr, -1);        
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        arr[key]=value;
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        return arr[key];
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        arr[key]=-1;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
    	int max = Integer.MIN_VALUE;
    	int count = 0;
    	for(int i=0;i<nums.length;i++) {
    		count += nums[i];
    		if (count>max)
    			max = count;
    		if (count<0)
    			count = 0;
    	}
    	return max;        
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int newSum = nums[0];
        int max = nums[0];
        for(int i=1;i<nums.length;i++) {
        	newSum = Math.max(newSum+nums[i], nums[i]);
        	max = Math.max(newSum, max);
        }
        return max;        
    }
}

class Solution {
    public int mySqrt(int x) {
		if (x < 0)
			return 0;
		else if (x < 2)
			return x;
		else {
			long smallCandidate = mySqrt(x >> 2) << 1;
			long largeCandidate = smallCandidate + 1;
			if (largeCandidate*largeCandidate > x)
				return new Long(smallCandidate).intValue();
			else
				return new Long(largeCandidate).intValue();
		}       
    }
}

class Solution {
    public int mySqrt(int x) {
		if (x==0 || x==1) return x;
		long i=1, result=1;
		while(result<=x) {
			i++;
			result = i*i;
		}
		return new Long(i-1).intValue();       
    }
}

class Solution {
    public int mySqrt(int x) {
		if (x == 0 || x == 1)
			return x;

		long start = 1, end = x, ans = 0;
		while (start <= end) {
			long mid = (start + end) / 2;

			if (mid * mid == x)
				return new Long(mid).intValue();

			if (mid * mid < x) {
				start = mid + 1;
				ans = mid;
			} else
				end = mid - 1;
		}
		return new Long(ans).intValue();       
    }
}