This documentation is automatically generated by online-judge-tools/verification-helper
# ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # verification-helper: PROBLEM https://judge.yosupo.jp/problem/range_affine_range_sum require "../src/lazy_seg_tree.cr" require "../src/mod_int.cr" _, q = read_line.split.map(&.to_i64) ais = read_line.split.map(&.to_i64) alias Mint = AtCoder::ModInt998244353 alias Segment = NamedTuple(sum: Mint, size: Int64) alias Affine = NamedTuple(b: Mint, c: Mint) op = ->(a : Segment, b : Segment) { {sum: a[:sum] + b[:sum], size: a[:size] + b[:size]} } mapping = ->(f : Affine, x : Segment) { {sum: f[:b] * x[:sum] + f[:c] * x[:size], size: x[:size]} } composition = ->(a : Affine, b : Affine) { {b: a[:b] * b[:b], c: b[:c] * a[:b] + a[:c]} } segments = ais.map { |a| {sum: Mint.new(a), size: 1_i64} } tree = AtCoder::LazySegTree(Segment, Affine).new(segments, op, mapping, composition) q.times do args = read_line.split.map(&.to_i64) if args[0] == 0 _, l, r, b, c = args tree[l...r] = {b: Mint.new(b), c: Mint.new(c)} else _, l, r = args p tree[l...r][:sum] end end
# ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # verification-helper: PROBLEM https://judge.yosupo.jp/problem/range_affine_range_sum # require "../src/lazy_seg_tree.cr" # ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. module AtCoder # Implements [atcoder::lazy_segtree](https://atcoder.github.io/ac-library/master/document_en/lazysegtree.html). # # The identity element will be implicitly defined as nil, so you don't # have to manually define it. In the other words, you cannot include # nil into an element of the monoid. # # Similarly, the identity map of F will be implicitly defined as nil, # so you don't have to manually define it. In the other words, you # cannot include nil into an element of the set F. # # ``` # op = ->(a : Int32, b : Int32) { [a, b].min } # mapping = ->(f : Int32, x : Int32) { f } # composition = ->(a : Int32, b : Int32) { a } # tree = AtCoder::LazySegTree(Int32, Int32).new((0...100).to_a, op, mapping, composition) # tree[10...50] # => 10 # tree[20...60] = 0 # tree[50...80] # => 0 # ``` class LazySegTree(S, F) @n : Int32 @height : Int32 @n_leaves : Int32 def initialize(values : Array(S), @operator : S, S -> S, @application : F, S -> S, @composition : F, F -> F) @n = values.size @height = log2_ceil(@n) @n_leaves = 1 << @height @segments = Array(S | Nil).new(2 * @n_leaves, nil) @applicators = Array(F | Nil).new(@n_leaves, nil) # initialize segments values.each_with_index { |x, i| @segments[@n_leaves + i] = x.as(S | Nil) } (@n_leaves - 1).downto(1) { |i| refresh(i) } end # Implements atcoder::lazy_segtree.set(index, applicator). def set(index : Int, value : S) index += @n_leaves @height.downto(1) { |j| propagate(ancestor(index, j)) } @segments[index] = value.as(S | Nil) (1..@height).each { |j| refresh(ancestor(index, j)) } end # Implements atcoder::lazy_segtree.apply(index, applicator). def []=(index : Int, applicator : F) index += @n_leaves @height.downto(1) { |j| propagate(ancestor(index, j)) } @segments[index] = apply(applicator, @segments[index]) (1..@height).each { |j| refresh(ancestor(index, j)) } applicator end # Implements atcoder::lazy_segtree.apply(left, right, applicator). # ameba:disable Metrics/CyclomaticComplexity def []=(range : Range, applicator : F) l = (range.begin || 0) + @n_leaves r = (range.exclusive? ? (range.end || @n_leaves) : (range.end || @n_leaves - 1) + 1) + @n_leaves @height.downto(1) do |i| propagate(ancestor(l, i)) if right_side_child?(l, i) propagate(ancestor(r - 1, i)) if right_side_child?(r, i) end l2, r2 = l, r while l2 < r2 if l2.odd? all_apply(l2, applicator) l2 += 1 end if r2.odd? r2 -= 1 all_apply(r2, applicator) end l2 >>= 1 r2 >>= 1 end (1..@height).each do |i| refresh(ancestor(l, i)) if right_side_child?(l, i) refresh(ancestor(r - 1, i)) if right_side_child?(r, i) end applicator end # Implements atcoder::lazy_segtree.get(index). def [](index : Int) index += @n_leaves @height.downto(1) { |j| propagate(ancestor(index, j)) } @segments[index].not_nil! end # Implements atcoder::lazy_segtree.prod(left, right). def [](range : Range) l = (range.begin || 0) + @n_leaves r = (range.exclusive? ? (range.end || @n_leaves) : (range.end || @n_leaves - 1) + 1) + @n_leaves @height.downto(1) do |i| propagate(ancestor(l, i)) if right_side_child?(l, i) propagate(ancestor(r - 1, i)) if right_side_child?(r, i) end sml, smr = nil.as(S | Nil), nil.as(S | Nil) while l < r if l.odd? sml = operate(sml, @segments[l]) l += 1 end if r.odd? r -= 1 smr = operate(@segments[r], smr) end l >>= 1 r >>= 1 end operate(sml, smr).not_nil! end # Implements atcoder::lazy_segtree.all_prod(). def all_prod self[0...@n] end # Implements atcoder::lazy_segtree.max_right(left, g). def max_right(left, e : S | Nil = nil, & : S -> Bool) unless 0 <= left && left <= @n raise IndexError.new("{left: #{left}} must greater than or equal to 0 and less than or equal to {n: #{@n}}") end unless e.nil? return nil unless yield e end return @n if left == @n left += @n_leaves @height.downto(1) { |i| propagate(ancestor(left, i)) } sm = e loop do while left.even? left >>= 1 end res = operate(sm, @segments[left]) unless res.nil? || yield res while left < @n_leaves propagate(left) left = 2*left res = operate(sm, @segments[left]) if res.nil? || yield res sm = res left += 1 end end return left - @n_leaves end sm = operate(sm, @segments[left]) left += 1 ffs = left & -left break if ffs == left end @n end # Implements atcoder::lazy_segtree.min_left(right, g). def min_left(right, e : S | Nil = nil, & : S -> Bool) unless 0 <= right && right <= @n raise IndexError.new("{right: #{right}} must greater than or equal to 0 and less than or equal to {n: #{@n}}") end unless e.nil? return nil unless yield e end return 0 if right == 0 right += @n_leaves @height.downto(1) { |i| propagate(ancestor(right - 1, i)) } sm = e loop do right -= 1 while right > 1 && right.odd? right >>= 1 end res = operate(@segments[right], sm) unless res.nil? || yield res while right < @n_leaves propagate(right) right = 2*right + 1 res = operate(@segments[right], sm) if res.nil? || yield res sm = res right -= 1 end end return right + 1 - @n_leaves end sm = operate(@segments[right], sm) ffs = right & -right break if ffs == right end 0 end @[AlwaysInline] private def operate(a : S | Nil, b : S | Nil) if a.nil? b elsif b.nil? a else @operator.call(a, b) end end @[AlwaysInline] private def apply(f : F | Nil, x : S | Nil) if f.nil? x elsif x.nil? nil else @application.call(f, x) end end @[AlwaysInline] private def compose(a : F | Nil, b : F | Nil) if a.nil? b elsif b.nil? a else @composition.call(a, b) end end @[AlwaysInline] private def refresh(node : Int) child1 = 2*node child2 = 2*node + 1 @segments[node] = operate(@segments[child1], @segments[child2]) end @[AlwaysInline] private def all_apply(node, applicator : F | Nil) @segments[node] = apply(applicator, @segments[node]) unless leaf?(node) @applicators[node] = compose(applicator, @applicators[node]) end end @[AlwaysInline] private def propagate(node : Int) child1 = 2*node child2 = 2*node + 1 all_apply(child1, @applicators[node]) all_apply(child2, @applicators[node]) @applicators[node] = nil end @[AlwaysInline] private def right_side_child?(child, n_gens_ago) ((child >> n_gens_ago) << n_gens_ago) != child end @[AlwaysInline] private def ancestor(node, n_gens_ago) node >> n_gens_ago end @[AlwaysInline] private def leaf?(node) node >= @n_leaves end @[AlwaysInline] private def log2_ceil(n : Int32) : Int32 sizeof(Int32)*8 - (n - 1).leading_zeros_count end end end # require "../src/mod_int.cr" # ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # require "./math.cr" # ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # require "./prime.cr" # ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # require "./math.cr" module AtCoder # Implements [Ruby's Prime library](https://ruby-doc.com/stdlib/libdoc/prime/rdoc/Prime.html). # # ``` # AtCoder::Prime.first(7) # => [2, 3, 5, 7, 11, 13, 17] # ``` module Prime extend self include Enumerable(Int64) @@primes = [ 2_i64, 3_i64, 5_i64, 7_i64, 11_i64, 13_i64, 17_i64, 19_i64, 23_i64, 29_i64, 31_i64, 37_i64, 41_i64, 43_i64, 47_i64, 53_i64, 59_i64, 61_i64, 67_i64, 71_i64, 73_i64, 79_i64, 83_i64, 89_i64, 97_i64, 101_i64, ] def each(&) index = 0 loop do yield get_nth_prime(index) index += 1 end end def prime_division(value : Int) raise DivisionByZeroError.new if value == 0 int = typeof(value) factors = [] of Tuple(typeof(value), typeof(value)) if value < 0 value = value.abs factors << {int.new(-1), int.new(1)} end until prime?(value) || value == 1 factor = value until prime?(factor) factor = find_factor(factor) end count = 0 while value % factor == 0 value //= factor count += 1 end factors << {int.new(factor), int.new(count)} end if value > 1 factors << {value, int.new(1)} end factors.sort_by! { |(factor, _)| factor } end private def find_factor(n : Int) # Factor of even numbers cannot be discovered by Pollard's Rho with f(x) = x^x+i if n.even? typeof(n).new(2) else pollard_rho(n).not_nil! end end # Get single factor by Pollard's Rho Algorithm private def pollard_rho(n : Int) typeof(n).new(1).upto(n) do |i| x = i y = pollard_random_f(x, n, i) loop do x = pollard_random_f(x, n, i) y = pollard_random_f(pollard_random_f(y, n, i), n, i) gcd = (x - y).gcd(n) if gcd == n break end if gcd != 1 return gcd end end end end @[AlwaysInline] private def pollard_random_f(n : Int, mod : Int, seed : Int) (AtCoder::Math.mul_mod(n, n, mod) + seed) % mod end private def extract_prime_division_base(prime_divisions_class : Array({T, T}).class) forall T T end def int_from_prime_division(prime_divisions : Array({Int, Int})) int_class = extract_prime_division_base(prime_divisions.class) prime_divisions.reduce(int_class.new(1)) { |i, (factor, exponent)| i * factor ** exponent } end def prime?(value : Int) # Obvious patterns return false if value < 2 return true if value <= 3 return false if value.even? return true if value < 9 if value < 0xffff return false unless typeof(value).new(30).gcd(value % 30) == 1 7.step(by: 30, to: value) do |base| break if base * base > value if {0, 4, 6, 10, 12, 16, 22, 24}.any? { |i| value % (base + i) == 0 } return false end end return true end miller_rabin(value.to_i64) end private def miller_rabin(value) d = value - 1 s = 0_i64 until d.odd? d >>= 1 s += 1 end miller_rabin_bases(value).each do |base| next if base == value x = AtCoder::Math.pow_mod(base.to_i64, d, value) next if x == 1 || x == value - 1 is_composite = s.times.all? do x = AtCoder::Math.mul_mod(x, x, value) x != value - 1 end return false if is_composite end true end # We can reduce time complexity of Miller-Rabin tests by testing against # predefined bases which is enough to test against primarity in the given range. # https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test # ameba:disable Metrics/CyclomaticComplexity private def miller_rabin_bases(value) case when value < 1_373_653_i64 [2, 3] when value < 9_080_191_i64 [31, 73] when value < 25_326_001_i64 [2, 3, 5] when value < 3_215_031_751_i64 [2, 3, 5, 7] when value < 4_759_123_141_i64 [2, 7, 61] when value < 1_122_004_669_633_i64 [2, 13, 23, 1662803] when value < 2_152_302_898_747_i64 [2, 3, 5, 7, 11] when value < 3_474_749_660_383_i64 [2, 3, 5, 7, 11, 13] when value < 341_550_071_728_321_i64 [2, 3, 5, 7, 11, 13, 17] when value < 3_825_123_056_546_413_051_i64 [2, 3, 5, 7, 11, 13, 17, 19, 23] else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] end end private def get_nth_prime(n) while @@primes.size <= n generate_primes end @@primes[n] end # Doubles the size of the cached prime array and performs the # Sieve of Eratosthenes on it. private def generate_primes new_primes_size = @@primes.size < 1_000_000 ? @@primes.size : 1_000_000 new_primes = Array(Int64).new(new_primes_size) { |i| @@primes.last + (i + 1) * 2 } new_primes_max = new_primes.last @@primes.each do |prime| next if prime == 2 break if prime * prime > new_primes_max # Here I use the technique of the Sieve of Sundaram. We can # only test against the odd multiple of the given prime. # min_composite is the minimum number that is greater than # the last confirmed prime, and is an odd multiple of # the given prime. min_multiple = ((@@primes.last // prime + 1) // 2 * 2 + 1) * prime min_multiple.step(by: prime * 2, to: new_primes_max) do |multiple| index = new_primes_size - (new_primes_max - multiple) // 2 - 1 new_primes[index] = 0_i64 end end @@primes.concat(new_primes.reject(0_i64)) end private struct EachDivisor(T) include Enumerable(T) def initialize(@exponential_factors : Array(Array(T))) end def each(&) Indexable.each_cartesian(@exponential_factors) do |factors| yield factors.reduce { |a, b| a * b } end end end # Returns an enumerator that iterates through the all positive divisors of # the given number. **The order is not guaranteed.** # Not in the original Ruby's Prime library. # # ``` # AtCoder::Prime.each_divisor(20) do |n| # puts n # end # => Puts 1, 2, 4, 5, 10, and 20 # # AtCoder::Prime.each_divisor(10).map { |n| 1.0 / n }.to_a # => [1.0, 0.5, 0.2, 0.1] # ``` def each_divisor(value : Int) raise ArgumentError.new unless value > 0 factors = prime_division(value) if value == 1 exponential_factors = [[value]] else exponential_factors = factors.map do |(factor, count)| cnt = typeof(value).zero + 1 Array(typeof(value)).new(count + 1) do |i| cnt_copy = cnt if i < count cnt *= factor end cnt_copy end end end EachDivisor(typeof(value)).new(exponential_factors) end # :ditto: def each_divisor(value : T, &block : T ->) each_divisor(value).each(&block) end end end struct Int def prime? AtCoder::Prime.prime?(self) end end module AtCoder # Implements [ACL's Math library](https://atcoder.github.io/ac-library/master/document_en/math.html) module Math def self.extended_gcd(a, b) zero = a.class.zero one = zero + 1 last_remainder, remainder = a.abs, b.abs x, last_x, y, last_y = zero, one, one, zero while remainder != 0 quotient, new_remainder = last_remainder.divmod(remainder) last_remainder, remainder = remainder, new_remainder x, last_x = last_x - quotient * x, x y, last_y = last_y - quotient * y, y end return last_remainder, last_x * (a < 0 ? -1 : 1) end # Implements atcoder::inv_mod(value, modulo). def self.inv_mod(value, modulo) gcd, inv = extended_gcd(value, modulo) if gcd != 1 raise ArgumentError.new("#{value} and #{modulo} are not coprime") end inv % modulo end # Simplified AtCoder::Math.pow_mod with support of Int64 def self.pow_mod(base, exponent, modulo) if exponent == 0 return base.class.zero + 1 end if base == 0 return base end b = exponent > 0 ? base : inv_mod(base, modulo) e = exponent.abs ret = 1_i64 while e > 0 if e % 2 == 1 ret = mul_mod(ret, b, modulo) end b = mul_mod(b, b, modulo) e //= 2 end ret end # Caluculates a * b % mod without overflow detection @[AlwaysInline] def self.mul_mod(a : Int64, b : Int64, mod : Int64) if mod < Int32::MAX return a * b % mod end # 31-bit width a_high = (a >> 32).to_u64 # 32-bit width a_low = (a & 0xFFFFFFFF).to_u64 # 31-bit width b_high = (b >> 32).to_u64 # 32-bit width b_low = (b & 0xFFFFFFFF).to_u64 # 31-bit + 32-bit + 1-bit = 64-bit c = a_high * b_low + b_high * a_low c_high = c >> 32 c_low = c & 0xFFFFFFFF # 31-bit + 31-bit res_high = a_high * b_high + c_high # 32-bit + 32-bit res_low = a_low * b_low res_low_high = res_low >> 32 res_low_low = res_low & 0xFFFFFFFF # Overflow if res_low_high + c_low >= 0x100000000 res_high += 1 end res_low = (((res_low_high + c_low) & 0xFFFFFFFF) << 32) | res_low_low (((res_high.to_i128 << 64) | res_low) % mod).to_i64 end @[AlwaysInline] def self.mul_mod(a, b, mod) typeof(mod).new(a.to_i64 * b % mod) end # Implements atcoder::crt(remainders, modulos). def self.crt(remainders, modulos) raise ArgumentError.new unless remainders.size == modulos.size total_modulo = 1_i64 answer = 0_i64 remainders.zip(modulos).each do |(remainder, modulo)| gcd, p = extended_gcd(total_modulo, modulo) if (remainder - answer) % gcd != 0 return 0_i64, 0_i64 end tmp = (remainder - answer) // gcd * p % (modulo // gcd) answer += total_modulo * tmp total_modulo *= modulo // gcd end return answer % total_modulo, total_modulo end # Implements atcoder::floor_sum(n, m, a, b). def self.floor_sum(n, m, a, b) n, m, a, b = n.to_i64, m.to_i64, a.to_i64, b.to_i64 res = 0_i64 if a < 0 a2 = a % m res -= n * (n - 1) // 2 * ((a2 - a) // m) a = a2 end if b < 0 b2 = b % m res -= n * ((b2 - b) // m) b = b2 end res + floor_sum_unsigned(n, m, a, b) end private def self.floor_sum_unsigned(n, m, a, b) res = 0_i64 loop do if a >= m res += n * (n - 1) // 2 * (a // m) a = a % m end if b >= m res += n * (b // m) b = b % m end y_max = a * n + b break if y_max < m n = y_max // m b = y_max % m m, a = a, m end res end # Returns `a * b > target`, without concern of overflows. def self.product_greater_than(a : Int, b : Int, target : Int) target // b < a end def self.get_primitive_root(p : Int) return 1_i64 if p == 2 n = p - 1 factors = AtCoder::Prime.prime_division(n) (2_i64..p.to_i64).each do |g| ok = true factors.each do |(factor, _)| if pow_mod(g, n // factor, p) == 1 ok = false break end end if ok return g end end raise ArgumentError.new end end end module AtCoder # Implements [atcoder::static_modint](https://atcoder.github.io/ac-library/master/document_en/modint.html). # # ``` # AtCoder.static_modint(ModInt101, 101_i64) # alias Mint = AtCoder::ModInt101 # Mint.new(80_i64) + Mint.new(90_i64) # => 89 # ``` macro static_modint(name, modulo) module AtCoder # Implements atcoder::modint{{modulo}}. # # ``` # alias Mint = AtCoder::{{name}} # Mint.new(30_i64) // Mint.new(7_i64) # ``` struct {{name}} {% if modulo == 998_244_353_i64 %} MOD = 998_244_353_i64 M = 998_244_353_u32 R = 3_296_722_945_u32 MR = 998_244_351_u32 M2 = 932_051_910_u32 {% elsif modulo == 1_000_000_007_i64 %} MOD = 1_000_000_007_i64 M = 1_000_000_007_u32 R = 2_068_349_879_u32 MR = 2_226_617_417_u32 M2 = 582_344_008_u32 {% else %} MOD = {{modulo}} {% end %} def self.zero new end @@factorials = Array(self).new def self.factorial(n) if @@factorials.empty? @@factorials = Array(self).new(100_000_i64) @@factorials << self.new(1) end @@factorials.size.upto(n) do |i| @@factorials << @@factorials.last * i end @@factorials[n] end def self.permutation(n, k) raise ArgumentError.new("k cannot be greater than n") unless n >= k factorial(n) // factorial(n - k) end def self.combination(n, k) raise ArgumentError.new("k cannot be greater than n") unless n >= k permutation(n, k) // @@factorials[k] end def self.repeated_combination(n, k) combination(n + k - 1, k) end def - self.class.new(0) - self end def + self end def +(value) self + self.class.new(value) end def -(value) self - self.class.new(value) end def *(value) self * self.class.new(value) end def /(value) raise DivisionByZeroError.new if value == 0 self / self.class.new(value) end def /(value : self) raise DivisionByZeroError.new if value == 0 self * value.inv end def //(value) self / value end def <<(value) self * self.class.new(2) ** value end def abs value end def pred self - 1 end def succ self + 1 end def zero? value == 0 end def to_i64 value end def ==(other : self) value == other.value end def ==(other) value == other end def sqrt z = self.class.new(1_i64) until z ** ((MOD - 1) // 2) == MOD - 1 z += 1 end q = MOD - 1 m = 0 while q.even? q //= 2 m += 1 end c = z ** q t = self ** q r = self ** ((q + 1) // 2) m.downto(2) do |i| tmp = t ** (2 ** (i - 2)) if tmp != 1 r *= c t *= c ** 2 end c *= c end if r * r == self r.to_i64 * 2 <= MOD ? r : -r else nil end end # ac-library compatibility def pow(value) self ** value end def val self.to_i64 end # ModInt shouldn't be compared def <(value) raise NotImplementedError.new("<") end def <=(value) raise NotImplementedError.new("<=") end def >(value) raise NotImplementedError.new(">") end def >=(value) raise NotImplementedError.new(">=") end {% if modulo == 998_244_353_i64 || modulo == 1_000_000_007_i64 %} getter mgy : UInt32 # Initialize using montgomery representation def self.raw(mgy : UInt32) ret = new ret.mgy = mgy ret end def initialize @mgy = 0 end def initialize(value : Int) @mgy = reduce(((value % M).to_u64 + M) * M2) end def clone ret = self.class.new ret.mgy = @mgy ret end def +(value : self) ret = self.class.raw(@mgy) ret.mgy = (ret.mgy.to_i64 + value.mgy - 2*M).to_u32! if ret.mgy.to_i32! < 0 ret.mgy = (ret.mgy.to_u64 + 2*M).to_u32! end ret end def -(value : self) ret = self.class.raw(@mgy) ret.mgy = (ret.mgy.to_i64 - value.mgy).to_u32! if ret.mgy.to_i32! < 0 ret.mgy = (ret.mgy.to_u64 + 2*M).to_u32! end ret end def *(value : self) ret = self.class.raw(@mgy) ret.mgy = reduce(ret.mgy.to_u64 * value.mgy) ret end def **(value) if value == 0 return self.class.new(1) end if self.zero? self end b = value > 0 ? self : inv e = value.abs ret = self.class.new(1) while e > 0 if e.odd? ret *= b end b *= b e >>= 1 end ret end def inv g, x = AtCoder::Math.extended_gcd(value.to_i32, M.to_i32) self.class.new(x) end def to_s(io : IO) io << value end def inspect(io : IO) to_s(io) end def mgy=(v : UInt32) @mgy = v end @[AlwaysInline] def reduce(b : UInt64) : UInt32 ((b + (b.to_u32!.to_u64 * MR).to_u32!.to_u64 * M) >> 32).to_u32 end @[AlwaysInline] def value ret = reduce(@mgy.to_u64) ret >= M ? (ret - M).to_i64 : ret.to_i64 end {% else %} getter value : Int64 def initialize(@value : Int64 = 0_i64) @value %= MOD end def initialize(value) @value = value.to_i64 % MOD end def clone self.class.new(@value) end def inv g, x = AtCoder::Math.extended_gcd(@value, MOD) self.class.new(x) end def +(value : self) self.class.new(@value + value.to_i64) end def -(value : self) self.class.new(@value - value.to_i64) end def *(value : self) self.class.new(@value * value.to_i64) end def **(value) self.class.new(AtCoder::Math.pow_mod(@value, value.to_i64, MOD)) end delegate to_s, to: @value delegate inspect, to: @value {% end %} end end struct Int def +(value : AtCoder::{{name}}) value + self end def -(value : AtCoder::{{name}}) -value + self end def *(value : AtCoder::{{name}}) value * self end def //(value : AtCoder::{{name}}) value.inv * self end def /(value : AtCoder::{{name}}) self // value end def ==(value : AtCoder::{{name}}) value == self end end end end AtCoder.static_modint(ModInt1000000007, 1_000_000_007_i64) AtCoder.static_modint(ModInt998244353, 998_244_353_i64) AtCoder.static_modint(ModInt754974721, 754_974_721_i64) AtCoder.static_modint(ModInt167772161, 167_772_161_i64) AtCoder.static_modint(ModInt469762049, 469_762_049_i64) _, q = read_line.split.map(&.to_i64) ais = read_line.split.map(&.to_i64) alias Mint = AtCoder::ModInt998244353 alias Segment = NamedTuple(sum: Mint, size: Int64) alias Affine = NamedTuple(b: Mint, c: Mint) op = ->(a : Segment, b : Segment) { {sum: a[:sum] + b[:sum], size: a[:size] + b[:size]} } mapping = ->(f : Affine, x : Segment) { {sum: f[:b] * x[:sum] + f[:c] * x[:size], size: x[:size]} } composition = ->(a : Affine, b : Affine) { {b: a[:b] * b[:b], c: b[:c] * a[:b] + a[:c]} } segments = ais.map { |a| {sum: Mint.new(a), size: 1_i64} } tree = AtCoder::LazySegTree(Segment, Affine).new(segments, op, mapping, composition) q.times do args = read_line.split.map(&.to_i64) if args[0] == 0 _, l, r, b, c = args tree[l...r] = {b: Mint.new(b), c: Mint.new(c)} else _, l, r = args p tree[l...r][:sum] end end