## HHPC1 P6 - Yarn Street's Strategic Shopping

View as PDF

Points: 20 (partial)
Time limit: 6.0s
Memory limit: 1G

Author:
Problem types

On Yarn Street, there are stores numbered from to , each selling a single item with cost . Throughout the day, shoppers walk along different segments of the street. The -th shopper will buy one item from each store numbered from to .

The local association offers coupons of value to attract shoppers. The -th shopper gets coupons. The coupons have specific stipulations:

• Each coupon can only be used once.
• At most one coupon can be used on each item, per shopper.
• The coupon can only be redeemed for items whose price are divisible by .
• Upon redemption, the item's price is divided by .

Shoppers aim to minimize the product of the total costs of items they purchase. For example, if a shopper purchases items with costs , , and , the product of the total costs is .

Your job is to assist each shopper in finding the minimum cost of their shopping trip if they are able to choose the optimal value of . Note that a coupon's price reduction only applies to the shopper who used them, and that not all coupons have to be used.

#### Input Specification

The first line contains an integer , the number of stores on Yarn Street.

The second line contains integers , indicating the cost of the item at each store.

The third line contains an integer , the number of shoppers.

The next lines each contain three integers, , , and , indicating that shopper travels from store to store with coupons.

#### Output Specification

For each of the people, find the minimal possible product and output that mod .

#### Sample Input

5
6 15 25 20 30
3
1 3 2
2 5 1
2 5 4

#### Sample Output

90
7500
360

#### Sample Explanation

The first person goes from store to store . The prices are , , and . By choosing and using coupons on items and , the prices become , , and . This leads to a minimal product of .

The second person goes from store to store .The prices are , , , and . By choosing and using coupons on the item , the prices become , , , and , leading to a minimal product of .

The third person also goes from store to store . The prices are , , , and . By choosing and using coupons on items , , and , the prices become , , , and , leading to a minimal product of .