Олимпиадный тренинг

Задача . B. Тенцинг и книги


Задача

Темы: битмаски жадные алгоритмы математика *1100

Тенцинг получил в подарок от фанатов \(3n\) книг. Книги расположены в \(3\) стопках по \(n\) книг в каждой стопке. У каждой книги есть неотрицательная целочисленная величина — сложность.

Тенцинг хочет прочитать несколько (возможно, ни одной) книги. Изначально его знание равно \(0\).

За один шаг Тенцинг выбирает непустую стопку, читает верхнюю книги в стопке и затем выкидывает ее. Если знание Тенцинга сейчас равно \(u\), то оно станет равно \(u|v\) после прочтения книги со сложностью \(v\). Здесь \(|\) обозначает операцию побитового ИЛИ. Тенцинг может прочитать произвольное количество книг и остановиться в любой момент.

Любимое число Тенцинга равно \(x\). Можете определить, может ли его знание стать равным \(x\)?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(x\) (\(1 \leq n \leq 10^5\), \(0 \leq x \leq 10^9\)) — количество книг в каждой стопке и любимое число Тенцинга.

Вторая строка содержит \(n\) целых чисел \(a_1,a_2,\ldots,a_n\) (\(0 \leq a_i \leq 10^9\)) — сложности книг в первой стопке сверху вниз.

Третья строка содержит \(n\) целых чисел \(b_1,b_2,\ldots,b_n\) (\(0 \leq b_i \leq 10^9\)) — сложности книг во второй стопке сверху вниз.

Четвертая строка содержит \(n\) целых чисел \(c_1,c_2,\ldots,c_n\) (\(0 \leq c_i \leq 10^9\)) — сложности книг в третьей стопке сверху вниз.

Гарантируется, что сумма значений \(n\) по всем наборам входных данных не превосходит \(10^5\).

Выходные данные

Для каждого набора входных данных выведите «Yes» (без кавычек), если Тенцинг может сделать свое знание равным \(x\), и «No» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Примечание

В первом примере Тенцинг может прочитать следующие \(4\) книги:

  • прочитать книгу со сложностью \(1\) сверху первой стопки. Знание становится равно \(0|1=1\).
  • прочитать книгу со сложностью \(1\) сверху третьей стопки. Знание становится равно \(1|1=1\).
  • прочитать книгу со сложностью \(2\) сверху первой стопки. Знание становится равно \(1|2=3\).
  • прочитать книгу со сложностью \(5\) сверху второй стопки. Знание становится равно \(3|5=7\).

После чтения этих книг знание Тенцинга равно \(7\).

В третьем примере Тенцинг может прочитать \(0\) книг, и его итоговое знание будет равно \(0\).


Примеры
№Входные данныеВыходные данные
1 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 
Yes
No
Yes

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет