// linear (N + N/2 + N/4 + ...)
public int codeOne(int n) {
	int sum = 0;
	for (int k = n; k > 0; k /= 2) {
		for (int i = 0; i < k; i++)
			sum++;
	}
	return sum;
}

// linear (1 + 2 + 4 + 8 + ...)
public int codeTwo(int n) {
	int sum = 0;
	for (int i = 1; i < n; i *= 2) {
		for (int j = 0; j < i; j++)
			sum++;
	}
	return sum;
}

// linearithmic (the outer loop loops lgN times)
public int codeThree(int n) {
	int sum = 0;
	for (int i = 1; i < n; i *= 2) {
		for (int j = 0; j < n; j++)
			sum++;
	}
	return sum;
}

public class Counter {
	private String name;
	private int count;
}

int[] a = new int[n];

int vInt = Integer.parseUnsignedInt("4294967295");
System.out.println(vInt); // -1
String sInt = Integer.toUnsignedString(vInt);
System.out.println(sInt); // 4294967295

double x1 = 0.3;
double x2 = 0.1 + 0.1 + 0.1;
System.out.println(x1 == x2); // false

double z1 = 0.5;
double z2 = 0.1 + 0.1 + 0.1 + 0.1 + 0.1;
System.out.println(z1 == z2); // true

public List<Integer> lexicalOrder(int n) {
	List<Integer> res = new ArrayList<>();
	for (int i = 1; i < 10; i++) {
		lexicalOrderDfs(i, n, res);
	}
	return res;
}

public void lexicalOrderDfs(int cur, int n, List<Integer> res) {
	if (cur > n)
		return;
	else {
		res.add(cur);
		for (int i = 0; i < 10; ++i) {
			lexicalOrderDfs(10 * cur + i, n, res);
		}
	}
}

public int titleToNumber(String s) {
	int ans = 0;
	for (int i = 0; i < s.length(); i++) {
		ans += ((s.charAt(i) - 'A') + 1) * Math.pow(26, s.length() - i - 1);
	}
	return ans;
}

public class UTF8Validation {
	public static boolean validateUtf8(int[] data) {
		if (data == null || data.length == 0)
			return false;
		boolean isValid = true;
		for (int i = 0; i < data.length; i++) {
			if (data[i] > 255)
				return false; // overflow, 1 after 8th digit, 100000000
			int numberOfBytes = 0;
			if ((data[i] & 128) == 0) { // 0xxxxxxx, 1 byte, 128(10000000)
				numberOfBytes = 1;
			} else if ((data[i] & 224) == 192) { // 110xxxxx, 2 bytes, 224(11100000), 192(11000000)
			//} else if ((data[i] & 0b11100000) == 0b11000000) { // or use bit format
				numberOfBytes = 2;
			} else if ((data[i] & 240) == 224) { // 1110xxxx, 3 bytes, 240(11110000), 224(11100000)
				numberOfBytes = 3;
			} else if ((data[i] & 248) == 240) { // 11110xxx, 4 bytes, 248(11111000), 240(11110000)
				numberOfBytes = 4;
			} else {
				return false;
			}
			for (int j = 1; j < numberOfBytes; j++) { // check that the next n bytes start with 10xxxxxx
				if (i + j >= data.length)
					return false;
				if ((data[i + j] & 192) != 128)
					return false; // 192(11000000), 128(10000000)
			}
			i = i + numberOfBytes - 1;
		}
		return isValid;
	}

	public static void main(String[] args) {
		// The octet sequence: 11000101 10000010 00000001.
		assert validateUtf8(new int[] { 197, 130, 1 }) == true;
		// The octet sequence: 11101011 10001100 00000100
		assert validateUtf8(new int[] { 235, 140, 4 }) == false;
	}
}

	public static String decodedToUtf8(String original, String charset) throws Exception {
		return new String(original.getBytes(charset), "UTF-8"); // say database is using ISO-8859-1
	}

	public static String decodeURLText(String urlText) {
		try {
			return URLDecoder.decode(urlText, "UTF-8");
		} catch (UnsupportedEncodingException e) {
			throw new RuntimeException(e);
		}
	}

	public static String encodeURLText(String urlText) {
		try {
			return URLEncoder.encode(urlText, "UTF-8").replace("+", "%20");
		} catch (UnsupportedEncodingException e) {
			throw new RuntimeException(e);
		}
	}

System.out.println("\u00AE \u00A7 \u00A9 \u00A4"); // they are characters: ® § © ¤

if (paramValue.contains("\u00A9")) {
	paramValue = paramValue.replace("\u00A9", "&copy");
	hasEntity = true;
}

public static int countBits(long x) {
	int count = 0;
	while (x != 0) {
		x &= (x - 1);
		count++;
	}
	return count;
}

/**
 * Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate
 * the number of 1's in their binary representation and return them as an array.
 */
public static int[] countBits2(int x) {
	int[] ans = new int[x + 1];
	// solution 1: last set bit
	for (int i = 1; i <= x; i++) {
		ans[i] = ans[i & (i - 1)] + 1;
	}
	// solution 2: least significant bit
	/*
	for (int i = 0; i <= x; i++) {
		ans[i] = ans[i >> 1] + (i & 1); // P(x) = P(x/2) + (x mod 2)
	}
	*/
	return ans;
}

public class BinaryIndexedTree {
  private int[] tree;

  public BinaryIndexedTree(int[] nums) {
    // Plus one to make tree easier to operate
    tree = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
      update(i, nums[i]);
    }
  }

  public int getSum(int index) {
    int sum = 0;
    index++; // index is 1 more than nums' length
    while (index > 0) {
      sum += tree[index];
      index -= (index & -index);
    }
    return sum;
  }

  // Add val to tree[i] and all of its ancestores
  public void update(int index, int val) {
    index++;
    while (index <= tree.length) {
      tree[index] += val;
      index += (index & -index);
    }
  }
}

public boolean getBit(int num, int i) {
	return (num & (1 << i)) != 0;
}

public int setBit(int num, int i) {
	return num | (1 << i);
}

public int clearBit(int num, int i) {
	return num & ~(1 << i);
	// clear all bits from the most significant bit through i (inclusive)
	// return num & ((1 << i) - 1);
	// clear all bits from i through 0 (inclusive)
	// return num & ((-1 << i + 1)); // NOTE: a sequence of 1 is -1
}

public int updateBit(int num, int i, boolean bitIs1) {
	int value = bitIs1 ? 1 : 0;
	int mask = ~(1 << i); // to clear bit
	return (num & mask) | (value << i);
}

public long swapBits(long x, int i, int j) {
	// extract the i-th and j-th bits, and see if they differ.
	if (((x >>> i) & 1) != ((x >>> j) & 1)) {
		long mask = (1L << i) | (1L << j); // combine
		x ^= mask; // flip their values with XOR
	}
	return x;
}

static void putInt(byte[] b, int off, int val) {
		b[off + 3] = (byte) (val       );
		b[off + 2] = (byte) (val >>>  8);
		b[off + 1] = (byte) (val >>> 16);
		b[off    ] = (byte) (val >>> 24);
}

static int getInt(byte[] b, int off) {
		return ((b[off + 3] & 0xFF)      ) +
					 ((b[off + 2] & 0xFF) <<  8) +
					 ((b[off + 1] & 0xFF) << 16) +
					 ((b[off    ]       ) << 24);
}

// Test the value of each bit while tracking the number of 1s seen so far.
// Complexity: O(n)
public short parity1(long x) {
	short result = 0;
	while (x != 0) {
		result ^= (x & 1); // store the number mod 2 since we only care if even or odd
		x >>>= 1;
	}
	return result;
}

// x & (x - 1) equals x with its lowest set bit erased.
// Complexity: O(k) k is the number of 1s.
public short parity2(long x) {
	short result = 0;
	while (x != 0) {
		result ^= 1;
		x &= (x - 1); // drops the lowest set bit of x
	}
	return result;
}

// The parity of (11010111) is the same as parity of (1101) XORed with (0111) which is (1010).
// Complexity: O(log(n))
public short parity3(long x) {
	for (int i = 32; i >= 1; i /= 2) {
		x ^= x >>> i;
	}
	return (short) (x & 0x1); // extract the last bit
}

// Especially for a long stream of words, like to compute CRC, we can cache precomputed parity.
// Complexity: O(n/L)
public short parity4(long x) {
	final int MASK_SIZE = 16;
	final int BIT_MASK = 0xFFFF;
	// feed in the precomputed parity
	final short[] precomputedParity = new short[2^16];
	return (short) (precomputedParity[(int) ((x >>> (3 * MASK_SIZE)) & BIT_MASK)]
			^ precomputedParity[(int) ((x >>> (2 * MASK_SIZE)) & BIT_MASK)]
			^ precomputedParity[(int) ((x >>> (MASK_SIZE)) & BIT_MASK)]
			^ precomputedParity[(int) (x & BIT_MASK)]);
}

	/**
	 * Reverse bits of a given 32 bits unsigned integer.
	 *
	 * For example, given input 43261596 (represented in binary as
	 * 00000010100101000001111010011100), return 964176192 (represented in binary as
	 * 00111001011110000010100101000000).
	 *
	 */
	public int reverseBits(int n) {
		int result = 0;
		for (int i = 0; i < 32; i++) {
			result += n & 1;
			n >>>= 1; // must do unsigned shift
			if (i < 31) // for last digit, don't shift!
				result <<= 1;
		}
		return result;
	}

	/**
	 * How to optimize if this function is called multiple times? We can divide an int into 4 bytes,
	 * and reverse each byte then combine into an int. For each byte, we can use cache to improve
	 * performance.
	 */
	private final Map<Byte, Integer> cache = new HashMap<Byte, Integer>();

	public int reverseBits2(int n) {
		int result = 0;
		for (int i = 0; i < 4; i++) {
			result += reverseByte((byte) ((n >>> 8 * i) & 0xFF)); // reverse per byte
			if (i < 3)
				result <<= 8;
		}
		return result;
	}

	private int reverseByte(byte b) {
		Integer value = cache.get(b); // first look up from cache
		if (value != null)
			return value;
		value = 0;
		// reverse by bit
		for (int i = 0; i < 8; i++) {
			value += ((b >>> i) & 1);
			if (i < 7)
				value <<= 1;
		}
		cache.put(b, value);
		return value;
	}

public static long reverseDigits(int x) {
	long result = 0;
	int remain = Math.abs(x);
	while (remain > 0) {
		result = result * 10 + remain % 10;
		remain /= 10;
	}
	return x < 0 ? -result : result;
}

public static long multiply(long x, long y) {
	long sum = 0;

	while (x != 0) {
		if ((x & 1) != 0) {
			sum = add(sum, y);
		}
		x >>>= 1;
		y <<= 1;
	}

	return sum;
}

// simple and easier code
private static long add(long a, long b) {
	long c = 0; // carrier
	while (b != 0) {
		c = a & b;
		a = a ^ b;
		b = c << 1;
	}
	return a;
}

private static long add2(long a, long b) {
	long sum = 0, carryin = 0, k = 1, tempA = a, tempB = b;
	while (tempA != 0 || tempB != 0) {
		long ak = a & k, bk = b & k;
		long carryout = (ak & bk) | (ak & carryin) | (bk & carryin);
		sum |= (ak ^ bk ^ carryin);
		carryin = carryout << 1;
		k <<= 1;
		tempA >>>= 1;
		tempB >>>= 1;
	}
	return sum | carryin;
}

public int add(int a, int b) {
		int c = 0;
		while (b != 0) {
				c = a & b;
				a = a ^ b;
				b = c << 1;
		}
		return a;
}

public static int divide(int x, int y) {
	if (y == 0)
		throw new IllegalArgumentException();
	int result = 0;
	int power = 32;
	long yPower = y << power;
	while (x >= y) {
		while (yPower > x) {
			yPower >>>= 1;
			power--;
		}
		result += 1 << power;
		x -= yPower;
	}
	return result;
}

// bottom-up recursive
public static double power(double x, int y) {
	double result = 1.0;

	long n = y; // avoid overflow, e.g., n = Integer.MIN_VALUE
	if (n < 0) {
		x = 1.0 / x;
		n = -n;
	}

	while (n != 0) {
		if ((n & 1) == 1) // will run twice for odd number, and only once for even number!
			result *= x;
		x *= x;
		n >>>= 1;
	}

	return result;
}

// top-down recursive
public static double powerII(double x, int y) {
	if (y == 0)
		return 1;
	if (y == 1)
		return x;

	if (y < 0) {
		y = -y;
		x = 1.0 / x;
	}

	int s = y >> 1; // divide by 2
	double half = powerII(x, s);

	if ((y & 1) == 0)
		return half * half;
	else
		return half * half * x;

}

/**
 * Given two binary strings, return their sum (also a binary string).
 *
 * For example, a = "11" b = "1" Return "100".
 *
 */
public class AddBinaryStrings {
	public String addBinary(String a, String b) {
		StringBuilder builder = new StringBuilder();
		int i = a.length() - 1;
		int j = b.length() - 1;
		int carry = 0;
		while (i >= 0 || j >= 0) {
			int sum = carry;
			if (i >= 0) {
				sum += a.charAt(i) - '0';
				i--;
			}
			if (j >= 0) {
				sum += b.charAt(j) - '0';
				j--;
			}
			builder.append(sum % 2);
			carry = sum / 2;
		}
		if (carry != 0)
			builder.append(carry);
		return builder.reverse().toString();
	}
}

/**
 * Find the closest integer with the same weight (the same number of bits set to 1)
 *
 * @param x
 * @return
 */
public static long closestIntSameBitCount(long x) {
	final int NUM_UNSIGNED_BITS = 63;
	// x is assumed to be non-negative so we know the leading bit is 0. We
	// restrict to our attention to 63 LSBs.
	for (int i = 0; i < NUM_UNSIGNED_BITS - 1; ++i) {
		if ((((x >>> i) & 1) != ((x >>> (i + 1)) & 1))) {
			x ^= (1L << i) | (1L << (i + 1)); // swaps bit-i and bit-(i + 1).
			return x;
		}
	}
	// throw error if all bits of x are 0 or 1.
	throw new IllegalArgumentException("All bits are 0 or 1");
}

/**
 * 16 + 10 + 36 = 62 bits in total!
 *
 * @param shardId
 *            contains 16 bits
 * @param typeId
 *            contains 10 bits
 * @param localId
 *            contains 36 bits
 * @return 64 bits ID
 */
public long encodeId(long shardId, long typeId, long localId) {
	return shardId << (10 + 36) | typeId << 36 | localId;
}

/**
 * @param id
 * @return shardId, typeId, localId
 */
public long[] decodeId(long id) {
	long[] result = new long[3];
	result[0] = (id >> 46) & 0xFFFF; // 1111,1111,1111,1111
	result[1] = (id >> 36) & 0x3FF; // 11,1111,1111
	result[2] = id & 0xFFFFFFFF;
	return result;
}

public int findIntegers(int num) {
	int[] f = new int[32];
	f[0] = 1; // first bit: 1
	f[1] = 2; // second bit: 10 01
	for (int i = 2; i < f.length; i++)
		f[i] = f[i - 1] + f[i - 2];
	int i = 30, sum = 0, prev_bit = 0;
	while (i >= 0) {
		if ((num & (1 << i)) != 0) {
			sum += f[i];
			if (prev_bit == 1) {
				sum--; // without including itself since it's invalid
				break;
			}
			prev_bit = 1;
		} else
			prev_bit = 0;
		i--;
	}
	return sum + 1; // include itself
}

/**
 * Write a program that takes an integer and determines if that integer's representation as a
 * decimal string is a palindrome.
 *
 * For example, return true for the inputs 0, 1, 7, 11, 121, 333, and 2147447412, and false for
 * the inputs -1, 12, 100.
 *
 * @param x
 * @return
 */
public static boolean isPalindromeNumber(int x) {
	if (x <= 0)
		return x == 0;

	final int numDigits = (int) (Math.floor(Math.log10(x))) + 1;
	int msdMask = (int) Math.pow(10, numDigits - 1);
	for (int i = 0; i < (numDigits / 2); i++) {
		if (x / msdMask != x % 10)
			return false;
		x %= msdMask; // remove the most significant digit of x.
		x /= 10; // remove the least significant digit of x.
		msdMask /= 100;
	}

	return true;
}

public static int uniformRandom(int lowerBound, int upperBound) {
	int result, numberOfOutcomes = upperBound - lowerBound + 1;

	do {
		result = 0;
		for (int i = 0; (1 << i) < numberOfOutcomes; i++) {
			result = (result << 1) | random.nextInt(2);
		}
	} while (result >= numberOfOutcomes);

	return result + lowerBound;
}

public class RectangleIntersection {
	static class Rectangle {
		int x, y, width, height;

		public Rectangle(int x, int y, int width, int height) {
			this.x = x;
			this.y = y;
			this.width = width;
			this.height = height;
		}
	}

	public static Rectangle intersectRectangle(Rectangle R1, Rectangle R2) {
		if (!isIntersect(R1, R2))
			return new Rectangle(0, 0, -1, -1); // no intersection

		int x = Math.max(R1.x, R2.x);
		int y = Math.max(R1.y, R2.y);
		int width = Math.min(R1.x + R1.width, R2.x + R2.width) - x;
		int height = Math.min(R1.y + R1.height, R2.y + R2.height) - y;
		return new Rectangle(x, y, width, height);
	}

	private static boolean isIntersect(Rectangle R1, Rectangle R2) {
		return R1.x <= R2.x + R2.width && R1.x + R1.width >= R2.x
			&& R1.y <= R2.y + R2.height && R1.y + R1.height >= R2.y;
	}

	public static void main(String[] args) {
		Rectangle R1, R2;
		R1 = new Rectangle(0, 0, 2, 2);
		R2 = new Rectangle(1, 1, 3, 3);
		Rectangle result = intersectRectangle(R1, R2);
		assert (result.x == 1 && result.y == 1 && result.width == 1 && result.height == 1);
		R1 = new Rectangle(0, 0, 1, 1);
		R2 = new Rectangle(1, 1, 3, 3);
		result = intersectRectangle(R1, R2);
		assert (result.x == 1 && result.y == 1 && result.width == 0 && result.height == 0);
		R1 = new Rectangle(0, 0, 1, 1);
		R2 = new Rectangle(2, 2, 3, 3);
		result = intersectRectangle(R1, R2);
		assert (result.x == 0 && result.y == 0 && result.width == -1 && result.height == -1);
	}
}

public class DesignBitVector {
	private static final int INT_SIZE = 32; // 4 bytes = 4 * 8 bits
	private int length;
	private int[] vector;

	public DesignBitVector(int length) {
		this.length = length;
		if (length % INT_SIZE == 0)
			vector = new int[length / INT_SIZE];
		else
			vector = new int[length / INT_SIZE + 1];
	}

	public int length() {
		return length;
	}

	public boolean get(int i) {
		if (i < 0 || i >= length)
			throw new ArrayIndexOutOfBoundsException(i);
		return (vector[i / INT_SIZE] & (1 << (i % INT_SIZE))) != 0;
	}

	public void set(int i, boolean flag) {
		if (i < 0 || i >= length)
			throw new ArrayIndexOutOfBoundsException(i);
		if (flag)
			vector[i / INT_SIZE] |= 1 << (i % INT_SIZE); // mask like: 1000
		else
			vector[i / INT_SIZE] &= ~(1 << (i % INT_SIZE)); // mask like: 0111
	}

	public void print() {
		for (int v : vector) {
			for (int i = 0; i < INT_SIZE; i++) {
				System.out.print((v >> i & 1) - 0);
			}
		}
		System.out.println();
	}

	public static void main(String[] args) {
		DesignBitVector bitVector = new DesignBitVector(10);
		bitVector.print();
		bitVector.set(1, true);
		bitVector.set(3, true);
		bitVector.set(5, true);
		bitVector.print();
		assert bitVector.get(3);
		assert !bitVector.get(4);
		assert bitVector.get(5);
		bitVector.set(1, false);
		bitVector.set(3, true);
		bitVector.set(5, false);
		bitVector.print();
		assert !bitVector.get(5);
	}
}

public class PowerOfTwo {
	// Divides by 2 until the quotient is odd or less than 1
	public static boolean isPowerOfTwo1(int x) {
		while ((x % 2 == 0) && x > 1) {
			x /= 2;
		}
		return x == 1;
	}

	// Compute each power of two incrementally until x is less than or equal to the value
	public static boolean isPowerOfTwo2(int x) {
		int powerOfTwo = 1;
		while (powerOfTwo < x && powerOfTwo < Integer.MAX_VALUE / 2) {
			powerOfTwo *= 2;
		}
		return x == powerOfTwo;
	}

	// Binary search of precomputed powers of two stored in an array
	// To improve multiple calls, declare powersOfTwo as global variable
	public static boolean isPowerOfTwo3(int x) {
		int[] powersOfTwo = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
				131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728,
				268435456, 536870912, 1073741824 };
		if (x == 0)
			return false;
		if (x == 1)
			return true;
		int left = 0, right = powersOfTwo.length - 1;
		while (left <= right) {
			int middle = left + (right - left) / 2;
			if (x == powersOfTwo[middle])
				return true;
			else if (x < powersOfTwo[middle])
				right = middle - 1;
			else
				left = middle + 1;
		}
		return false;
	}

	// Counting 1 bits until more than 1 bit found
	public static boolean isPowerOfTwo4(int x) {
		int numOfOneBits = 0;
		while (x > 0 && numOfOneBits <= 1) {
			if ((x & 1) == 1)
				numOfOneBits++;
			x >>= 1;
		}
		return numOfOneBits == 1;
	}

	// Remove all right 0 bits, equivalent of the divide by two
	public static boolean isPowerOfTwo5(int x) {
		while ((x & 1) == 0 && x > 1) {
			x >>= 1;
		}
		return x == 1;
	}

	// Shortcut: Decrement and Compare
	public static boolean isPowerOfTwo6(int x) {
		return (x != 0) && (x & (x - 1)) == 0;
	}

	// Shortcut: Complement and Compare
	public static boolean isPowerOfTwo7(int x) {
		return (x != 0) && (x & (~x + 1)) == x;
	}

	public static void main(String[] args) {
		assert isPowerOfTwo1(524288) == true;
		assert isPowerOfTwo1(16392) == false;
		assert isPowerOfTwo2(524288) == true;
		assert isPowerOfTwo2(16392) == false;
		assert isPowerOfTwo3(524288) == true;
		assert isPowerOfTwo3(16392) == false;
		assert isPowerOfTwo4(524288) == true;
		assert isPowerOfTwo4(16392) == false;
		assert isPowerOfTwo5(524288) == true;
		assert isPowerOfTwo5(16392) == false;
		assert isPowerOfTwo6(524288) == true;
		assert isPowerOfTwo6(16392) == false;
		assert isPowerOfTwo7(524288) == true;
		assert isPowerOfTwo7(16392) == false;
	}
}

public class XorTwoNums {
	class TreeNode {
		int val;
		TreeNode zero, one;
		boolean isEnd;
	}

	class TrieTree {
		TreeNode root;

		public TrieTree() {
			this.root = new TreeNode();
		}

		public void insert(int num) {
			TreeNode current = root;
			int j = 1 << 30;
			while (j > 0) {
				int b = (j & num) == 0 ? 0 : 1;
				if (b == 0 && current.zero == null)
					current.zero = new TreeNode();
				else if (b == 1 && current.one == null)
					current.one = new TreeNode();
				current = b == 0 ? current.zero : current.one;
				j >>= 1;
			}
			current.val = num;
			current.isEnd = true;
		}

	}

	public int findMaximumXOR(int[] nums) {
		if (nums.length < 2)
			return 0;
		TrieTree tree = new TrieTree();
		for (int num : nums) {
			tree.insert(num);
		}
		TreeNode now = tree.root;
		while (now.one == null || now.zero == null)
			now = now.one == null ? now.zero : now.one;
		return findMaximumXOR(now.zero, now.one);
	}

	public int findMaximumXOR(TreeNode zero, TreeNode one) {
		if (zero.isEnd && one.isEnd)
			return one.val ^ zero.val;
		if (zero.zero == null)
			return findMaximumXOR(zero.one, one.zero == null ? one.one : one.zero);
		else if (zero.one == null)
			return findMaximumXOR(zero.zero, one.one == null ? one.zero : one.one);
		else if (one.zero == null)
			return findMaximumXOR(zero.zero, one.one);
		else if (one.one == null)
			return findMaximumXOR(zero.one, one.zero);
		else // split to 2 branches
			return Math.max(findMaximumXOR(zero.zero, one.one), findMaximumXOR(zero.one, one.zero));
	}

	public static void main(String[] args) {
		XorTwoNums solution = new XorTwoNums();
		assert solution.findMaximumXOR(new int[] { 8, 10, 2 }) == 10;
	}
}

public int islandPerimeter(int[][] grid) {
	if (grid.length == 0 || grid[0].length == 0)
		return 0;
	int perimeter = 0;
	for (int i = 0; i < grid.length; i++) {
		for (int j = 0; j < grid[i].length; j++) {
			if (grid[i][j] == 1) {
				perimeter += 4;
				if (i >= 1 && grid[i - 1][j] == 1)
					perimeter -= 2; // minus the inner joined up neighbors
				if (j >= 1 && grid[i][j - 1] == 1)
					perimeter -= 2; // minus the inner joined left neighbors
			}
		}
	}
	return perimeter;
}

public int maxAreaOfIsland(int[][] grid) {
		boolean[][] seen = new boolean[grid.length][grid[0].length];
		int ans = 0;
		for (int r = 0; r < grid.length; r++) {
				for (int c = 0; c < grid[0].length; c++) {
						ans = Math.max(ans, extendArea(r, c, grid, seen));
				}
		}
		return ans;
}

public int extendArea(int r, int c, int[][] grid, boolean[][] seen) {
		if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || seen[r][c] || grid[r][c] == 0) // NOTE: grid[r][c] == 0
				return 0;
		seen[r][c] = true;
		return (1 + extendArea(r + 1, c, grid, seen) + extendArea(r - 1, c, grid, seen)
						+ extendArea(r, c - 1, grid, seen) + extendArea(r, c + 1, grid, seen));
}

int[][] dirs = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };

public int numIslands(char[][] grid) {
	if (grid == null || grid.length == 0)
		return 0;
	int count = 0;
	for (int i = 0; i < grid.length; i++) {
		for (int j = 0; j < grid[i].length; j++) {
			if (grid[i][j] == '1') {
				count++;
				clearJoinedLands(grid, i, j);
			}
		}
	}
	return count;
}

private void clearJoinedLands(char[][] grid, int i, int j) {
	if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0')
		return;
	grid[i][j] = '0';
	for (int[] dir : dirs) {
		clearJoinedLands(grid, i + dir[0], j + dir[1]);
	}
	return;
}

int[][] dirs = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };

public int numDistinctIslands(int[][] grid) {
	Set<String> islands = new HashSet<>();
	for (int i = 0; i < grid.length; i++) {
		for (int j = 0; j < grid[i].length; j++) {
			if (grid[i][j] != 0) {
				StringBuilder sb = new StringBuilder();
				dfs(grid, i, j, sb, "o"); // origin
				// grid[i][j] = 0;
				islands.add(sb.toString());

			}
		}
	}
	return islands.size();
}

private void dfs(int[][] grid, int i, int j, StringBuilder sb, String dir) {
	if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == 0)
		return;
	sb.append(dir);
	grid[i][j] = 0;
	dfs(grid, i - 1, j, sb, "u");
	dfs(grid, i, j + 1, sb, "r");
	dfs(grid, i + 1, j, sb, "d");
	dfs(grid, i, j - 1, sb, "l");
	sb.append("b"); // bound
}

int[][] dirs = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };

	public int numIslands2(char[][] grid) {
		if (grid == null || grid.length == 0)
			return 0;
		int count = 0;

		int m = grid.length;
		int n = grid[0].length;
		int[] roots = new int[m * n];
		Arrays.fill(roots, -1);

		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				if (grid[i][j] == '1') {
					int root = n * i + j;
					roots[root] = root;
					count++;

					for (int[] dir : dirs) {
						int x = i + dir[0];
						int y = j + dir[1];
						int neighbor = n * x + y;
						if (x < 0 || x >= m || y < 0 || y >= n || roots[neighbor] == -1)
							continue;
						int rootNeighbor = findRootIsland(roots, nb);
						if (root != rootNeighbor) {
							roots[root] = rootNeighbor; // union two islands
							root = rootNeighbor;
							count--;
						}
					}
				}
			}
		}

		return count;
	}

	private int findRootIsland(int[] roots, int id) {
		while (id != roots[id]) {
			roots[id] = roots[roots[id]]; // compress path
			id = roots[id];
		}
		return id;
	}

/**
 * Given a binary string s and an integer k.
 * 
 * Return true if every binary code of length k is a substring of s. Otherwise, return false.
 * 
 * 
 * 
 * Example 1:
 * 
 * Input: s = "00110110", k = 2 <br>
 * Output: true <br>
 * Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as
 * substrings at indicies 0, 1, 3 and 2 respectively.
 * 
 * Solution: With rolling hash method, we only need O(1) to calculate the next hash, because bitwise
 * operations (&, <<, |, etc.) are only cost O(1).
 *
 */
public class ContainsBinaryCodes {
  public static boolean hasAllCodes(String s, int k) {
    int need = 1 << k;
    boolean[] got = new boolean[need];
    int allOne = need - 1;
    int hashVal = 0;

    for (int i = 0; i < s.length(); i++) {

      hashVal = ((hashVal << 1) & allOne) | (s.charAt(i) - '0');
      // hash only available when i-k+1 > 0
      if (i >= k - 1 && !got[hashVal]) {
        got[hashVal] = true;
        need--;
        if (need == 0) {
          return true;
        }
      }
    }
    return false;
  }
}

  public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    if (desiredTotal <= maxChoosableInteger) {
      return true;
    }
    if (maxChoosableInteger * (1 + maxChoosableInteger) / 2.0 < desiredTotal) {
      return false;
    }
    return canIWin(0, new Boolean[1 << maxChoosableInteger], desiredTotal, maxChoosableInteger);
  }

  // State is the bitmap representation of the all picked/chosen integers
  // dp[state] represents whether the current player can win the game at this state
  private boolean canIWin(int state, Boolean[] dp, int desiredTotal, int maxChoosableInteger) {
    if (dp[state] != null) {
      return dp[state];
    }
    for (int i = 1; i <= maxChoosableInteger; i++) {
      int current = 1 << (i - 1);
      // 0 means i is not used
      if ((current & state) == 0) {
        // check whether this leads to a win:
        // 1. i is greater than the desired total
        // 2. the other player can't win after the current player picks i
        if (i >= desiredTotal || !canIWin(state | current, dp, desiredTotal - i, maxChoosableInteger)) {
          dp[state] = true;
          return dp[state];
        }
      }
    }
    dp[state] = false;
    return dp[state];
  }

/**
 * 
 * A wonderful string is a string where at most one letter appears an odd number of times.
 * 
 * For example, "ccjjc" and "abab" are wonderful, but "ab" is not. Given a string word that consists
 * of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful
 * non-empty substrings in word. If the same substring appears multiple times in word, then count
 * each occurrence separately.
 * 
 * A substring is a contiguous sequence of characters in a string.
 * 
 * <pre>
 * Example 1:
 * 
 * Input: word = "aba"
 * Output: 4
 * Explanation: The four wonderful substrings are underlined below:
 * - "aba" -> "a"
 * - "aba" -> "b"
 * - "aba" -> "a"
 * - "aba" -> "aba"
 * </pre>
 * 
 * https://leetcode.com/problems/number-of-wonderful-substrings/
 */
public class WonderfulSubstrings {

  public long wonderfulSubstrings(String word) {
    long result = 0;
    // Store frequency of all bitmask combinations from 0b0000000000 to 0b1111111111
    long[] freqMap = new long[1 << ('j' - 'a') + 1]; // max 1024 combinations
    // Set frequency of 0000000000 as 1 when no element was encountered
    freqMap[0] = 1;

    int bitMask = 0;
    for (char c : word.toCharArray()) {
      // Toggling bit of current character to make it from odd to even OR even to odd
      bitMask ^= 1 << (c - 'a');
      // The substring between previous and current bitmask has even characters
      // Add the frequency of previous bitMask as they can all combine with current char
      result += freqMap[bitMask];

      // The substring between previous and current bitmask has odd characters.
      for (char i = 'a'; i <= 'j'; i++) {
        result += freqMap[bitMask ^ 1 << (i - 'a')];
      }

      // Increasing frequency of the current bitmask for future
      freqMap[bitMask]++;
    }

    return result;
  }
}