Food Quiz
本题没有可用的提交语言。
Description
As the chef of a highly-successive restaurant, you have so many wonderful dishes on your menu that your diners can't figure out what to order! To help them, you created a multiple-choice quiz that has $n$ questions, each with $m$ answer choices. The $i$th answer choice for each question choice has value $v_i$. There are also $q$ different types of food.
When taking a quiz, a diner chooses exactly one choice per question. They then add up the corresponding values for each question and get some final score $S$. The $k$th food has some associated interval $[l_k, r_k]$, and each pair of intervals is disjoint. If $l_k \leq S \leq r_k$, then the quiz determines that the diner should order $k$th food.
After making the quiz, you want to make sure it is actually possible to get any of the foods as the result of the quiz. For each of the $q$ foods, can you help figure out if it is possible to pick some combination of answer choices and get a score that is within the interval for that food?
The first line contains integers $n$ and $m$ ($1 \leq n, m \leq 20$) – the number of questions in the quiz and the number of answer choices per question.
The second line contains $m$ integers $v_1, v_2, \dots, v_m$ ($1 \leq v_i \leq 20$) – the values for each of the answer choices.
The third line contains the integer $q$ ($1 \leq q \leq 20$) – the number of possible food choices.
The following $q$ lines contain integers $l_i, r_i$ ($0 \leq l_i \leq r_i \leq 20n$) – the interval $[l_i, r_i]$ in which the score must lie to pick food $i$. You are guaranteed that for $i \neq j$, then $[l_i, r_i]$ and $[l_j, r_j]$ do not intersect, i.e. the intervals are pairwise disjoint.
For each food, output "YES" (without quotes) if it is possible to pick that food, and "NO" otherwise.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
Input
The first line contains integers $n$ and $m$ ($1 \leq n, m \leq 20$) – the number of questions in the quiz and the number of answer choices per question.
The second line contains $m$ integers $v_1, v_2, \dots, v_m$ ($1 \leq v_i \leq 20$) – the values for each of the answer choices.
The third line contains the integer $q$ ($1 \leq q \leq 20$) – the number of possible food choices.
The following $q$ lines contain integers $l_i, r_i$ ($0 \leq l_i \leq r_i \leq 20n$) – the interval $[l_i, r_i]$ in which the score must lie to pick food $i$. You are guaranteed that for $i \neq j$, then $[l_i, r_i]$ and $[l_j, r_j]$ do not intersect, i.e. the intervals are pairwise disjoint.
Output
For each food, output "YES" (without quotes) if it is possible to pick that food, and "NO" otherwise.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
1 3
1 3 5
6
1 1
2 2
3 3
4 4
5 5
6 20
2 4
2 3 4 5
3
12 20
1 3
6 11
Yes
No
Yes
No
Yes
No
No
No
Yes