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.

#### Constraints

For all subtasks:

##### Subtask 1 [20%]

##### Subtask 2 [30%]

##### Subtask 3 [50%]

No additional constraints.

#### 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 .

## Comments