D - AND and SUM Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

T 個のテストケースについて、以下の問題を解いてください。

非負整数 a,s が与えられます。以下の条件を両方とも満たす非負整数の組 (x,y) は存在しますか？

  • x\ \text{AND}\ y=a
  • x+y=s
\text{AND} とは

非負整数 n, m の bit ごとの論理積 n\ \text{AND}\ m は、以下のように定義されます。

  • n\ \text{AND}\ m を二進表記した際の 2^k \, (k \geq 0) の位の数は、n, m を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。
例えば、4\ \text{AND}\ 6 = 4 となります（二進表記すると: 100\ \text{AND}\ 110 = 100）。

制約

  • 1 \leq T \leq 10^5
  • 0 \leq a,s \lt 2^{60}
  • 入力はすべて整数

入力

入力は標準入力から与えられる。入力の 1 行目は以下の形式である。

T

その後、 T 個のテストケースが続く。各テストケースは以下の形式で与えられる。

a s

出力

T 行出力せよ。i\ (1 \leq i \leq T) 行目には、i 番目に与えられるテストケースについて問題文中の条件を両方とも満たす非負整数の組 (x,y) が存在するなら Yes を、存在しないなら No を出力せよ。

入力例 1

2
1 8
4 2

出力例 1

Yes
No

1 番目のテストケースにおいては、(x,y)=(3,5) などが条件を満たします。

2 番目のテストケースにおいては、条件を満たす非負整数の組 (x,y) は存在しません。

入力例 2

4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

出力例 2

No
Yes
Yes
No

Score : 400 points

Problem Statement

Solve the following problem for T test cases.

Given are non-negative integers a and s. Is there a pair of non-negative integers (x,y) that satisfies both of the conditions below?

  • x\ \text{AND}\ y=a
  • x+y=s
What is bitwise \mathrm{AND}?

The bitwise \mathrm{AND} of integers A and B, A\ \mathrm{AND}\ B, is defined as follows:

  • When A\ \mathrm{AND}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if those of A and B are both 1, and 0 otherwise.
For example, we have 4\ \mathrm{AND}\ 6 = 4 (in base two: 100\ \mathrm{AND}\ 110 = 100).

Constraints

  • 1 \leq T \leq 10^5
  • 0 \leq a,s \lt 2^{60}
  • All values in input are integers.

Input

Input is given from Standard Input. The first line is in the following format:

T

Then, T test cases follow. Each test case is in the following format:

a s

Output

Print T lines. The i-th line (1 \leq i \leq T) should contain Yes if, in the i-th test case, there is a pair of non-negative integers (x,y) that satisfies both of the conditions in the Problem Statement, and No otherwise.

Sample Input 1

2
1 8
4 2

Sample Output 1

Yes
No

In the first test case, some pairs such as (x,y)=(3,5) satisfy the conditions.

In the second test case, no pair of non-negative integers satisfies the conditions.

Sample Input 2

4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

Sample Output 2

No
Yes
Yes
No