PERFUME - Perfume

no tags 

 

One of the largest perfume shops is making perfumes by mixing fragrant
essential oils with other compounds. The shop representative told you that what
really matters in the mixture is the percentages of two main components (call
them A and B), all other stuff is complementary. For example their first sold
perfume had 10% of component A and 35% of component B, while the most
successful one had 16% of A and 20% of B. Sometimes the store needs to
create a new mixture with specific percentages of A and B and they wonder if
this can be achieved by mixing some of the mixtures they already have and this
is where they need your help. For example a new mixture which has 12% of A
and 30% of B can be created by mixing the two mixtures above in the ratio 2:1,
while it is impossible to create a mixture which has 13% of A and 22% of B
using the same two mixtures.

 

One of the largest perfume shops is making perfumes by mixing fragrant essential oils with other compounds. The shop representative told you that what really matters in the mixture is the percentages of two main components (call them A and B), all other stuff is complementary. For example their first sold perfume had 10% of component A and 35% of component B, while the most successful one had 16% of A and 20% of B. Sometimes the store needs to create a new mixture with specific percentages of A and B and they wonder if this can be achieved by mixing some of the mixtures they already have and this is where they need your help. For example a new mixture which has 12% of A and 30% of B can be created by mixing the two mixtures above in the ratio 2:1, while it is impossible to create a mixture which has 13% of A and 22% of B using the same two mixtures.

 

 

Input

 

The first line contains T <= 100, the number of test cases. The first line of each test case contains an integer (1 <= N <= 200), the number of mixtures the shop already has. The next N lines each contain two floating point numbers (0 <= A, B <= 100, A+B <= 100) representing the percentages of components A and B in each mixture. The next line contains an integer (1 <= Q <= 5151) the number of mixtures to verify. The next Q lines each contain two floating point numbers (0 <= A, B <= 100, A+B <= 100) representing the percentages of components A and B in each new mixture. Test cases are separated by one or more empty lines.

 

Output

 

For each mixture query print "Yes" if the new mixture can be created from the already existent ones or "No" otherwise. Print a blank line between test cases.

 

Example

Input:
2
2
10.0000 35.0000
16.0000 20.0000
2
12.0000 30.0000
13.0000 22.0000
3 10 35 16 20 7 15 1 13 22 Output: Yes No

Yes

hide comments
felipenoronha: 2020-02-01 18:24:38

Its geometry

zetro: 2010-11-27 02:52:12

@Mohammad Kotb: actually i almost get the point of this problem...but there is something that make me confused.....may you give me some hint......


Added by:Mohammad Kotb
Date:2010-08-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: OBJC VB.NET
Resource:ENC09