#P18391. Mercenaries

Mercenaries

Mercenaries

有n座从左到右编号为1到n的城市,相邻城市间有一条只能向右通行的道路。第i座城市有一名初始力量为s_i、魔法知识为m_i的雇佣兵。

连接城市i与i+1的道路上有一家商店,出售r_i件物品。第j件物品提供力量加成s'{i,j}和魔法加成m'{i,j}。雇佣兵经过一家商店时,最多购买其中一件物品;经过不同商店获得的加成可以全部累加。

每个独立场景给出v、a、b、c,表示城市v受到攻击。选择出发城市j≤v,其雇佣兵沿途购买物品后,属性为S、M;若aS+bM≥c,则可以获胜。也允许j=v,此时没有机会购买物品。

对每个场景,输出能够获胜的最大出发城市编号j。如果不存在,输出-1。场景之间完全独立,雇佣兵和商店不会因前面的场景发生变化。

输入格式

第一行一个整数n,2≤n≤200000。

接下来的2n−1行交替描述城市和道路商店:

  • 对i=1..n,第2i−1行给出s_i、m_i,均在[0,10^9]内。
  • 对i=1..n−1,第2i行先给出r_i,再给出r_i对s'{i,j}、m'{i,j}。1≤r_i≤500000,每种加成均在[0,5000]内,且所有商店的商品总数R=Σr_i≤500000。

随后一行一个整数q,1≤q≤200000。

接下来q行,每行四个整数v、a、b、c,满足1≤v≤n,0≤a,b≤10^9,a+b≥1,1≤c≤10^18。

输出格式

输出q行,每行一个整数,表示相应场景的最大可行出发城市编号,或者-1。

样例

样例输入 1

3
1 1
2 1 2 1 2
3 2
5 1 5 4 3 3 4 5 1 1 2
4 5
12
1 1 1 1
2 1 1 1
3 1 1 1
3 1 1 9
3 2 2 20
3 1 2 18
3 1 2 19
3 1 2 20
3 0 1 8
2 1 0 4
2 1 0 3
2 1 0 2

样例输出 1

1
2
3
3
2
2
1
-1
1
-1
2
2

说明

第六个场景,从城市2出发并购买第二家商店的(1,5),最终属性为(4,7),战力为4+2×7=18,恰好获胜。城市1出发也能获胜,但答案取更靠右的2。

第七个场景,城市1的雇佣兵购买(1,2)和(1,5),最终属性为(3,8),战力为19,答案为1。第八个场景要求战力至少20,没有可行雇佣兵。