/*
* Time Spent: 
	0. Expect: min
	1. Idea: 
	2. Code: 
* Solution: 
	Tag: 
	https://www.cnblogs.com/CloudWings/p/18324122
* Summary: 
*/
bool query (int);
void modify (int, bool);
bool WereYouLast (int n, int m) {
	if (m == 10) {  // 只有 10 位不够维护奇偶性，但是题目允许每次修改 10 个 bit，那就直接维护 n 了
		int pos = 0;
		for (int i = 1; i <= m; i++)
			pos = (pos<<1) | query(i);
		if (++pos == n) return 1;
		for (int i = m; i && pos; i--, pos >>= 1)
			modify(i, pos & 1);
		return 0;
	}
	if (query(m)) return 1;
	int len = 0, pos = 0;
	while (n) len++, n >>= 1;
	len--;
	for (int i = 1; i <= 5; i++)
		pos = (pos<<1) | query(i);
	pos++;
	if (query(5+pos)) {
		modify(5+pos, 0);
		int t = pos;
		for (int i = 5; i && t; i--, t >>= 1)
			modify(i, t&1);
	} else {
		if (pos == len) {  // 第 n-1 次打个特殊标记。
			modify(m, 1);
		} else {
			modify(5+pos, 1);
			for (int i = 1; i <= 5; i++)
				modify(i, 0);
		}
	}
	return 0;
}
/*
g++ _1.cpp -o _1 -O2 -std=c++11 -DLOCAL; ./_1.exe
*/