int bitcnt(LL x)
{
	int c = 0;
	for(; x; x>>=1)
		c += x&1;
	return c;
}


/* for every nonempty subset of S  : O(2^|S|)
 for(int sub=S; sub; sub=(sub-1)&S) { ... }

*/
