Algorithms and Data Structures

Advanced Subset Sum Queries

Given a set of n numbers , you are asked to perform 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 s from 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 elements of the set.
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 t is 1 and the second integer s represents the target sum.
  • For a Type 2 query, the first integer t is 2 and the second integer s represents 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: 8 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue