Advanced Subset Sum Queries
Given a set of
n numbers q queries. Each query is one of the two types:- Type 1: Determine whether there exists a subset of numbers that sum up to
s.
- Type 2: Remove the given number
sfrom the set.
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 300), the size of the set of numbers. The second line contains n space-separated integers The third line of the input contains a single integer
q , the number of queries. The next q lines each contain two space-separated integers, t, and s :- For a Type 1 query, the first integer
tis 1 and the second integersrepresents the target sum.
- For a Type 2 query, the first integer
tis 2 and the second integersrepresents the element that should be removed.
The number of Type 2 queries does not exceed 200
Output
For each Type 1 query, output
Yes if such a subset exists, otherwise output No.Examples
Input | Output |
4
1 2 5 7
7
1 4
1 3
1 10
2 1
1 10
1 3
1 9 | No
Yes
Yes
No
No
Yes |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB