HHPC1 P6 - Yarn Street's Strategic Shopping

View as PDF

Submit solution

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

Problem types

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

The local association offers coupons of value p to attract shoppers. The i-th shopper gets k_i 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 p.
  • Upon redemption, the item's price is divided by p.

Shoppers aim to minimize the product of the total costs of items they purchase. For example, if a shopper purchases items with costs 2, 3, and 7, the product of the total costs is 2 \times 3 \times 7 = 42.

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 p. Note that a coupon's price reduction only applies to the shopper who used them, and that not all coupons have to be used.


For all subtasks:

1 \le N \le 3 \times 10^5

1 \le M \le 5 \times 10^4

1 \le c_i \le 10^6

1 \le l \le r \le N

1 \le k \le 10

Subtask 1 [20%]

1\le N \le 5 \times 10^4

1\le c_i \le 10^5

Subtask 2 [30%]

1\le N \le 10^5

Subtask 3 [50%]

No additional constraints.

Input Specification

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

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

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

The next M lines each contain three integers, l_i, r_i, and k_i, indicating that shopper i travels from store l to store r with k_i coupons.

Output Specification

For each of the M people, find the minimal possible product and output that mod 10^9+7.

Sample Input

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

Sample Output


Sample Explanation

The first person goes from store 1 to store 3. The prices are 6, 15, and 25. By choosing p=5 and using coupons on items 2 and 3, the prices become 6, 3, and 5. This leads to a minimal product of 90.

The second person goes from store 2 to store 5.The prices are 15, 25, 20, and 30. By choosing p=30 and using coupons on the item 5, the prices become 15, 25, 20, and 1, leading to a minimal product of 7500.

The third person also goes from store 2 to store 5. The prices are 15, 25, 20, and 30. By choosing p=5 and using coupons on items 2, 3, 4 and 5, the prices become 3, 5, 4, and 6, leading to a minimal product of 360.


There are no comments at the moment.