#P18949. [Mladen Manev 2021 B2] stocks / 区间中的最低预测价格

[Mladen Manev 2021 B2] stocks / 区间中的最低预测价格

区间中的最低预测价格

有 NN 个资产,第 ii 个资产在第一个月的价格为 ViV_i,此后每个月增加 DiD_i。因此它在第 KK 个月的价格为 Vi+(K−1)DiV_i+(K-1)D_i。

处理 QQ 个询问 (L,R,K)(L,R,K):求第 KK 个月,编号在 [L,R][L,R] 内的资产的最低价格。

输入格式

第一行整数 NN。接下来 NN 行,第 ii 行为 Vi,DiV_i,D_i。随后一行整数 QQ,再接下来 QQ 行,每行为 L,R,KL,R,K。

输出格式

每个询问输出一行最低价格。答案需要使用 64 位整数。

数据范围

1≤N,Q≤1051\le N,Q\le10^5,1≤L≤R≤N1\le L\le R\le N,1≤Vi,Di,K≤1091\le V_i,D_i,K\le10^9。

样例

3
1 5
4 3
5 4
3
1 2 3
2 3 1
1 3 5
10
4
16

来源与数据说明

2021 年 Dr. Mladen Manev,B2,原题名 stocks。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。