310491: CF1842B. Tenzing and Books

B. Tenzing and Bookstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Tenzing received $3n$ books from his fans. The books are arranged in $3$ stacks with $n$ books in each stack. Each book has a non-negative integer difficulty rating.

Tenzing wants to read some (possibly zero) books. At first, his knowledge is $0$.

To read the books, Tenzing will choose a non-empty stack, read the book on the top of the stack, and then discard the book. If Tenzing's knowledge is currently $u$, then his knowledge will become $u|v$ after reading a book with difficulty rating $v$. Here $|$ denotes the bitwise OR operation. Note that Tenzing can stop reading books whenever he wants.

Tenzing's favourite number is $x$. Can you help Tenzing check if it is possible for his knowledge to become $x$?

Input

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 10^5$, $0 \leq x \leq 10^9$) — the number of books in each stack and Tenzing's favourite number.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq 10^9$)  — the difficulty rating of the books in the first stack, from top to bottom.

The third line of each test case contains $n$ integers $b_1,b_2,\ldots,b_n$ ($0 \leq b_i \leq 10^9$)  — the difficulty rating of the books in the second stack, from top to bottom.

The fourth line of each test case contains $n$ integers $c_1,c_2,\ldots,c_n$ ($0 \leq c_i \leq 10^9$)  — the difficulty rating of the books in the third stack, from top to bottom.

It is guaranteed that the sum of $n$ does not exceed $10^5$.

Output

For each test case, output "Yes" (without quotes) if Tenzing can make his knowledge equal to $x$, and "No" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

3
5 7
1 2 3 4 5
5 4 3 2 1
1 3 5 7 9
5 2
3 2 3 4 5
5 4 3 2 1
3 3 5 7 9
3 0
1 2 3
3 2 1
2 2 2

Output

Yes
No
Yes

Note

For the first test case, Tenzing can read the following $4$ books:

• read the book with difficulty rating $1$ on the top of the first stack. Tenzing's knowledge changes to $0|1=1$.
• read the book with difficulty rating $1$ on the top of the third stack. Tenzing's knowledge changes to $1|1=1$.
• read the book with difficulty rating $2$ on the top of the first stack. Tenzing's knowledge changes to $1|2=3$.
• read the book with difficulty rating $5$ on the top of the second stack. Tenzing's knowledge changes to $3|5=7$.

After reading all books, Tenzing's knowledge is $7$.

For the third test case, Tenzing can read $0$ books to make his final knowledge equals to $0$.

题目大意：
Tenzing收到了来自粉丝的3n本书，这些书被分成3堆，每堆n本。每本书都有一个非负整数的难度等级。Tenzing的知识初始为0。他可以选择一个非空的书堆，阅读顶部的一本书，然后丢弃这本书。如果Tenzing当前的知识是u，那么他阅读难度等级为v的书后，他的知识将变为u|v。这里|表示按位或操作。Tenzing可以在任何时候停止阅读书籍。Tenzing最喜欢的数字是x，请帮助Tenzing判断他的知识是否可能变成x。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和x（1≤n≤10^5，0≤x≤10^9），分别表示每堆书的数量和Tenzing最喜欢的数字。
- 接下来的三行，每行包含n个整数（0≤ai≤10^9），分别表示三个书堆从顶部到底部的书的难度等级。

输出：
- 对于每个测试用例，如果Tenzing可以使他的知识等于x，则输出"Yes"（不包含引号），否则输出"No"。
- 输出答案时大小写不敏感，例如"yEs"、"yes"、"Yes"和"YES"都会被识别为肯定的回答。题目大意： Tenzing收到了来自粉丝的3n本书，这些书被分成3堆，每堆n本。每本书都有一个非负整数的难度等级。Tenzing的知识初始为0。他可以选择一个非空的书堆，阅读顶部的一本书，然后丢弃这本书。如果Tenzing当前的知识是u，那么他阅读难度等级为v的书后，他的知识将变为u|v。这里|表示按位或操作。Tenzing可以在任何时候停止阅读书籍。Tenzing最喜欢的数字是x，请帮助Tenzing判断他的知识是否可能变成x。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n和x（1≤n≤10^5，0≤x≤10^9），分别表示每堆书的数量和Tenzing最喜欢的数字。 - 接下来的三行，每行包含n个整数（0≤ai≤10^9），分别表示三个书堆从顶部到底部的书的难度等级。 输出： - 对于每个测试用例，如果Tenzing可以使他的知识等于x，则输出"Yes"（不包含引号），否则输出"No"。 - 输出答案时大小写不敏感，例如"yEs"、"yes"、"Yes"和"YES"都会被识别为肯定的回答。