public static void precal() {
		int root, child, lim = (1 << 19);
		a = new int[lim + 1];
		v = new boolean[lim + 1];
		lim *= 2;
		for (int i = 1; i < a.length; i++) {
			root = child = 1;
			while (child * 2 < lim) {
				child *= 2;
				if (v[root])
					child++;
				v[root] = !v[root];
				root = child;
			}
			a[i] = child;
		}
	}