李逍遥终于迎来与拜月教主的决战，只见拜月教主召唤出了 nnn 只水魔兽，第 iii 只的水魔兽的体力值为 a[i]a[i]a[i]. 李逍遥在寻找水魔兽的弱点，由于御剑术威力过大会消耗掉全身真气，因此他每次会选择一个区间 [l,r][l, r][l,r] 假想发动御剑术来查询此次造成的伤害值（并不会对水魔兽造成实质伤害）. 对于区间 [l,r][l, r][l,r] 的水魔兽，御剑术的伤害值计
李逍遥终于迎来与拜月教主的决战，只见拜月教主召唤出了 nnn 只水魔兽，第 iii 只的水魔兽的体力值为 a[i]a[i]a[i]. 李逍遥在寻找水魔兽的弱点，由于御剑术威力过大会消耗掉全身真气，因此他每次会选择一个区间 [l,r][l, r][l,r] 假想发动御剑术来查询此次造成的伤害值（并不会对水魔兽造成实质伤害）. 对于区间 [l,r][l, r][l,r] 的水魔兽，御剑术的伤害值计算规则为：构造非空正整数序列 sss 满足 ∏s=∏i=lra[i]begin{aligned} prod{s} = prod_{i=l}^{r}{a[i]} end{aligned}∏s=i=l∏ra[i]，则伤害值为 min{∑s}minleft{sum{s}right}min{∑s}. 拜月教主也不甘示弱，他每次会挑选一个区间 [l,r][l, r][l,r] 和整数 xxx，使得区间 [l,r][l, r][l,r] 水魔兽的体力值变成 xxx 倍，即 ∀i∈[l,r]a[i]←a[i]×xforall_{i in [l, r]}{a[i] leftarrow a[i] times x}∀i∈[l,r]a[i]←a[i]×x. 由于李逍遥正忙着对付拜月教主，所以请你帮他计算伤害值。
（图片来源网络，侵删）
