我在一家饼干工厂工作。
这家工厂生产名为“ARC-tan 饼干”的可爱饼干。
该工厂有 有 N ARC-Tan 饼干制作机,制作机包括 它的编号最大为 1 从 N 。每台机器都有不同的口味设置,因此可以区分不同机器制作的饼干。此外,为每台制造机器设置一次生成的cookie数量。机器一次性生成指定数量的cookie。
最近,在我工作的工厂,M 我们决定进行两天的工厂参观。每天,将执行以下任务之一:
- 进行游览。在参观中,我们将看到具有特定连续编号的制造机器,该编号是每天确定的。 1 我们计划一次操作一台机器,并将这些机器生产的所有饼干分发给旅游参与者作为纪念品。
- 进行维护,并按每天确定的一定数量增加或减少一定连续数量的制造机器的数量。
由于工厂很大,很容易迷路,所以每个参观日期都有固定的参观人数。
这里的工厂经理不喜欢不可分割的东西,除非他将相同数量的任何一台机器制作的饼干分发给当天所有的游客,否则他就不会满意。另外,请不要做任何可怜的事情,例如不赠送一些ARC-tan饼干或压碎它们。换句话说,所有制作的饼干必须平均分配给旅游客人。另一方面,为了宣传这个工厂,我们希望在满足这些条件的同时,接待尽可能多的旅游游客。
作为策划者,在每个巡演日期,1 我们决定找出每次旅行可以参加的旅行顾客的最大数量。不过,我正忙于开发新口味。所以我希望你能解决这个问题。
入力
N a_1 a_2 … a_N M t_1 l_1 r_1 t_2 l_2 r_2 : t_M l_M r_M
- 1 行是一个整数,表示制造机器的数量。 给出 N (1≦N≦100,000) 给出。
- 2 在线 N 整数,用空格分隔。
- 整数 a_i (1≦a_i≦10^9) 是一台制造机器 i (1≦i≦N) 代表初始状态下产生的cookie数量。
- 3 行是一个整数,表示游览和维护的天数。 来自行 M (1≦M≦100,000) 给出。
- 4 从行 M 代表游览和维护过程。 3 整数由空格分隔。
- 整数 t_i (-10^9<t_i<10^9) 是总计 i (1≦i≦M) 代表每天要做的工作。
- t_i=0 表示该巡演将在当天举行。
- t_i≠0 表示当天进行维护。
- 至少 1 有些日子会举办旅行团。
- 整数 l_i,r_i (1≦l_i≦r_i≦N) 是总计 i 表示有关当天工作的详细信息。
- 如果当天是旅行团的举办日,则人数 表示游览期间将使用 l_i , l_i+1, ... , r_i 制造机器。
- 如果当天是进行维护的日期,则数量 表示将对 l_i , l_i+1, ... , r_i 制造机器进行维护。 如果t_i 为正,则计算制造的每台制造机器的数量。 增加 t_i , 如果t_i 为负数,则生产数量 -t_i 维护期间执行增量减少量的过程。
- 在所有维护日,维护后任何机器产生的 cookie 数量都会减少。 1 枚以上 10^9 或更少。
部分点
- 仅包含满足以下条件的测试用例,30 有一组点。
- 所有整数 在 i (1≦i≦M) 中,t_i≠0 如果 l_i=r_i 成立。
- 通过正确回答包括上述设置在内的所有测试用例,剩余的 70 可以获得积分。
出力
游览次数 T 。此时的输出为 仅输出 T 行。i 行表示从第一天开始的数字。 i 输出第一个旅游日期可以邀请的最大游客人数。
请在输出末尾添加换行符。
入力例 1
4 6 3 38 49 7 0 1 3 -2 3 3 0 1 3 9 2 2 0 1 2 6 3 3 0 3 4
出力例 1
1 3 6 7
- 初始状态下每台机器生产的饼干数量为1 从制造机器编号开始 6,3,38,49 。
- 1 当天将举行巡演。
- 制造机器巡回演出 使用 1,2,3 ,因此产生的cookie数量为 6,3,38 变为。
- 在这种情况下,游客 1 只能接受人。
- 2 维护将于第二天进行。 生产编号
- 製造機 3 减少 2 。维护后产生的cookie数量为1 从制造机器编号开始 6,3,36,49 变为。
- 3 当天将举行巡演。
- 制造机器巡回演出 使用 1,2,3 ,因此产生的cookie数量为 6,3,36 变为。
- 在这种情况下,游客可以 3 人们被接受。 增加
- 4 维护将于第二天进行。 生产编号
- 製造機 2 减少 9 。维护后产生的cookie数量为1 从制造机器编号开始 6,12,36,49 变为。
- 5 当天将举行巡演。
- 制造机器巡回演出 使用 1,2 ,因此产生的cookie数量为 6,12 变为。
- 在这种情况下,游客可以 6 人们被接受。 增加
- 6 维护将于第二天进行。 生产编号
- 製造機 3 减少 6 。维护后产生的cookie数量为1 从制造机器编号开始 6,12,42,49 变为。
- 7 当天将举行巡演。
- 制造机器巡回演出 使用 3,4 ,因此产生的cookie数量为 42,49 变为。
- 在这种情况下,游客可以 7 人们被接受。 增加
入力例 2
3 1 3 17 6 16 1 1 8 2 2 0 1 2 0 2 2 6 2 2 0 1 3
出力例 2
1 11 17
- 在此测试用例中 4 旅行当天,旅行当天运行的制造机器为 1 有时这只是一件事。