Майк получил в подарок на день рождения массив $$$a$$$ длины $$$n$$$ и решил протестировать, насколько он красивый.
Массив пройдет $$$i$$$-й тест на красоту, если существует способ из изначального массива путем некоторого (возможно, нулевого) количества операций разреза получить массив с суммой элементов, равной $$$s_i$$$.
Операция разреза массива происходит следующим образом:
- Вычисляется $$$mid = \lfloor\frac{max(array) + min(array)}{2}\rfloor$$$, где $$$max$$$ и $$$min$$$ — это функции нахождения максимального и минимального элемента массива. Иными словами, $$$mid$$$ равно сумме максимального и минимального элементов $$$array$$$, деленной на $$$2$$$ с округлением вниз.
- Далее массив разделяется на две части $$$\mathit{left}$$$ и $$$right$$$. В $$$\mathit{left}$$$ попадают все элементы массива, которые имеют значение меньшее либо равное $$$mid$$$, а в массив $$$right$$$ попадают все элементы, которые больше $$$mid$$$. Элементы в $$$\mathit{left}$$$ и $$$right$$$ сохраняют свой относительный порядок, который был в $$$array$$$.
- Третьим шагом выбирается, какой из массивов $$$\mathit{left}$$$ или $$$right$$$ мы хотим оставить. Выбранный массив заменит собой текущий, а другой навсегда удалится.
Вам требуется помочь Майку определить результаты $$$q$$$ тестов на красоту.
Заметьте, что вы тестируете красоту массива $$$a$$$, поэтому вы начинаете каждый тест на красоту с изначальным (заданным) массивом $$$a$$$. Таким образом, первый разрез (если он необходим) всегда совершается над массивом $$$a$$$.
Каждый тест содержит один или несколько наборов входных данных. В первой строке записано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 100$$$).
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ $$$(1 \le n, q \le 10^5)$$$ — длину массива $$$a$$$ и количество тестов на красоту соответственно.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^6)$$$ — описание массива $$$a$$$.
Следующие $$$q$$$ строк каждого набора входных данных содержат по одному целому числу $$$s_i$$$ $$$(1 \le s_i \le 10^9)$$$ — сумму элементов, которую хочет добиться Майк в $$$i$$$-м тесте на красоту.
Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ не превосходят $$$10^5$$$ ($$$\sum n, \sum q \le 10^5$$$).
Для каждого набора входных данных выведите $$$q$$$ строк, каждая из которых должна содержать «Yes», если соответствующий тест на красоту пройден, и «No» в противном случае.
2 5 5 1 2 3 4 5 1 8 9 12 6 5 5 3 1 3 1 3 1 2 3 9 11
Yes No Yes No Yes No Yes No Yes Yes
Объяснение первого набора входных данных:
- Получить массив с суммой $$$s_1 = 1$$$ мы можем следующим способом:
1.1 $$$a = [1, 2, 3, 4, 5]$$$, $$$mid = \frac{1+5}{2} = 3$$$, $$$\mathit{left} = [1, 2, 3]$$$, $$$right = [4, 5]$$$. Мы выбираем оставить массив $$$\mathit{left}$$$.
1.2 $$$a = [1, 2, 3]$$$, $$$mid = \frac{1+3}{2} = 2$$$, $$$\mathit{left} = [1, 2]$$$, $$$right = [3]$$$. Мы выбираем оставить массив $$$\mathit{left}$$$.
1.3 $$$a = [1, 2]$$$, $$$mid = \frac{1+2}{2} = 1$$$, $$$\mathit{left} = [1]$$$, $$$right = [2]$$$. Мы выбираем оставить массив $$$\mathit{left}$$$ с суммой, равной $$$1$$$.
- Массив с суммой $$$s_2 = 8$$$ можно показать, что получить невозможно.
- Получить массив с суммой $$$s_3 = 9$$$ мы можем следующим способом:
3.1 $$$a = [1, 2, 3, 4, 5]$$$, $$$mid = \frac{1+5}{2} = 3$$$, $$$\mathit{left} = [1, 2, 3]$$$, $$$right = [4, 5]$$$. Мы выбираем оставить массив $$$right$$$ с суммой, равной $$$9$$$.
- Массив с суммой $$$s_4 = 12$$$ можно показать, что получить невозможно.
- Получить массив с суммой $$$s_5 = 6$$$ мы можем следующим способом:
5.1 $$$a = [1, 2, 3, 4, 5]$$$, $$$mid = \frac{1+5}{2} = 3$$$, $$$\mathit{left} = [1, 2, 3]$$$, $$$right = [4, 5]$$$. Мы выбираем оставить массив $$$\mathit{left}$$$ с суммой, равной $$$6$$$.
Объяснение второго набора входных данных:
- Массив с суммой $$$s_1 = 1$$$ можно показать, что получить невозможно.
- Получить массив с суммой $$$s_2 = 2$$$ мы можем следующим способом:
2.1 $$$a = [3, 1, 3, 1, 3]$$$, $$$mid = \frac{1+3}{2} = 2$$$, $$$\mathit{left} = [1, 1]$$$, $$$right = [3, 3, 3]$$$. Мы выбираем оставить массив $$$\mathit{left}$$$ с суммой $$$2$$$.
- Массив с суммой $$$s_3 = 3$$$ можно показать, что получить невозможно.
- Получить массив с суммой $$$s_4 = 9$$$ мы можем следующим способом:
4.1 $$$a = [3, 1, 3, 1, 3]$$$, $$$mid = \frac{1+3}{2} = 2$$$, $$$\mathit{left} = [1, 1]$$$, $$$right = [3, 3, 3]$$$. Мы выбираем оставить массив $$$right$$$ с суммой $$$9$$$.
- Мы можем получить $$$s_5 = 11$$$ без операций разреза, потому что изначальная сумма уже была равна $$$11$$$.
