Description

The father-in-law gives an array $a$ indexed from $1$, where initially $a_i = 2^{i-1}$.

The mother-in-law asks Xiao L to perform the following operations several times:

In the $i$-th operation, choose two numbers $u_i, v_i\ (2 \le u_i < v_i)$, then execute sequentially:

• $a_{v_i} \gets a_{v_i} + a_{u_i} + a_{u_i - 1}$
• $a_{u_i} \gets -\infty$
• $a_{u_i - 1} \gets -\infty$

The first operation has no special restrictions, but for each subsequent operation, it must satisfy $v_i > v_{i-1}$.

Given $T$ queries, each with two numbers $k$ and $x$, determine whether it's possible to make $a_k = x$ through a finite number of operations.

The queries are independent (i.e., the array $a$ should be reset after each query).

Input Format

Due to large input size, it's recommended to use fast input methods.

The input consists of $T + 1$ lines:

• The first line contains a positive integer $T$, the number of queries.
• The next $T$ lines each contain two positive integers $k$ and $x$, representing a query.

Output Format

Output a binary string of length $T$.
The $i$-th character of the string indicates the answer to the $i$-th query:

• 1 if it's possible to make $a_k = x$;
• 0 otherwise.

4
6 36
6 35
5 30
5 31

0101

Hint

For $100\%$ of the data:

• $1 \le T \le 5 \times 10^6$
• $1 \le k \le 60$
• $0 \le x \le 4 \times 10^{18}$

Special Property A: Guarantees $x = 2^{k} - 1$.

Please optimize your code for constant factors.

The time and memory limits are at least 2.5 times those of the standard solution (with fast I/O).

Due to large input/output volume, we strongly recommend using fast I/O templates.

char *p1,*p2,buf[1<<20];
inline char gc(){if(p1==p2)p2=(p1=buf)+fread(buf,1,1<<20,stdin);return p1==p2?' ':*p1++;}
inline long long read(){
	register long long s=0; register char c=gc();
	while(c<'0'||c>'9') c=gc();
	while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^48),c=gc();
	return s;
}

x = read() //input x

Translation by DeepSeek R1