macro pt(s);pointerof({{s}});end struct Time;def diff(other : Time);(self-other).abs.total_milliseconds;end;end struct Bool;def to_i;self ? 1 : 0;end;end macro vgen(*v);Array.new({{v[0]}}){ {% if v.size==2 %}{{v[1]}}{% else %}vgen({{v[1..].splat}}){% end %} };end macro rvgen(type,*v);{% if v.size==2 %}Array({{type}}).new({{v[0]}}){{{v[1]}}}{% else %}Array.new({{v[0]}}){rvgen({{type}},{{v[1..].splat}})}{% end %};end def max(a,b);a%t ? ({{a}}=%t;true) : false);end macro chmax(a,b);(%t={{b}};{{a}}<%t ? ({{a}}=%t;true) : false);end macro swap(a,b);{{a}},{{b}}={{b}},{{a}};end def assert(cond : Bool, msg = "Assertion failed");raise msg unless cond;end TF = {true, false} def yn(cond) ios.outl cond ? "Yes" : "No" end macro for(f, m, s);begin {{f}} while {{m}} begin {{yield}} ensure {{s}} end end end;end struct Int def each_subset(&) s = self loop do yield s s = s - 1 & self break if s == self end end end module Indexable(T) def [](c : Bool); self[c ? 1 : 0]; end def []=(c : Bool, v : T); self[c ? 1 : 0] = v; end end require "big" lib LibIOset fun memcpy(dest : Void*, src : Void*, n : UInt64) : Void* fun write(fd : Int32, buf : Void*, count : UInt64) : Int64 fun mmap(addr : Void*, len : UInt64, prot : Int32, flags : Int32, fd : Int32, offset : Int64) : Void* end class IOset BUFS = 1 << 20 OT = Pointer(UInt32).malloc(10000) POW10 = {1i64, 10i64, 100i64, 1000i64, 10000i64, 100000i64, 1000000i64, 10000000i64, 100000000i64, 1000000000i64, 10000000000i64, 100000000000i64, 1000000000000i64, 10000000000000i64, 100000000000000i64 , 1000000000000000i64, 10000000000000000i64} REV = StaticArray(UInt32, 10).new(0u32) @obuf = Pointer(UInt8).malloc BUFS; @precision = 10 @ptr : UInt8*; @end : UInt8*; @optr : UInt8*; @oend : UInt8* def initialize 10u32.times { |a| 10.times { |b| 10.times { |c| 10.times { |d| OT[a * 1000 + b * 100 + c * 10 + d] = a + 48 | b + 48 << 8 | c + 48 << 16 | d + 48 << 24 } } } } sz = IO::FileDescriptor.new(0).info.size.to_u64 @ptr = LibIOset.mmap(Pointer(Void).null, sz, 1, 2, 0, 0i64).as(UInt8*) @end = @ptr + sz @optr = @obuf @oend = @obuf + BUFS end def eof? : Bool @ptr == @end end def read_byte : UInt8? return nil if @ptr == @end; b = @ptr.value; @ptr += 1; b end def trim : Nil while @ptr < @end && @ptr.value <= 32 @ptr += 1 end end def trim? : Bool trim @ptr < @end end def getc : Char trim raise "End of file reached (IOset.getc)" if @ptr == @end c = @ptr.value; @ptr += 1 c.chr end def read_line : String raise "End of file reached (IOset.read_line)" if @ptr == @end start = @ptr while @ptr < @end && @ptr.value != 10 @ptr += 1 end len = @ptr - start @ptr += 1 if @ptr < @end String.new(start, len) end def gets : String trim raise "End of file reached (IOset.gets)" if @ptr == @end start = @ptr while @ptr < @end && @ptr.value > 32 @ptr += 1 end String.new(start, @ptr - start) end def gets? : String? trim return nil if @ptr == @end start = @ptr while @ptr < @end && @ptr.value > 32 @ptr += 1 end String.new(start, @ptr - start) end macro geti_g(name, type) def {{name}} : {{type}} trim sign = 1 if @ptr.value == 45 sign = -1; @ptr += 1 end n = {{type}}.zero while @ptr + 8 <= @end tmp = @ptr.as(UInt64*).value break if ((tmp &-= 0x3030303030303030_u64) & 0x8080808080808080_u64) != 0 tmp = (tmp &* 10 &+ (tmp >> 8)) & 0x00ff00ff00ff00ff_u64 tmp = (tmp &* 100 &+ (tmp >> 16)) & 0x0000ffff0000ffff_u64 tmp = (tmp &* 10000 &+ (tmp >> 32)) & 0x00000000ffffffff_u64 n = n &* 100000000 &+ tmp @ptr += 8 end while @ptr < @end c = @ptr.value &- 48u8 break if 9u8 < c n = n &* 10 &+ c @ptr += 1 end n &* sign end end geti_g(geti8, Int8); geti_g(getu8, UInt8); geti_g(geti16, Int16); geti_g(getu16, UInt16) geti_g(geti, Int32); geti_g(getu, UInt32); geti_g(getbi, BigInt) geti_g(geti64, Int64); geti_g(getu64, UInt64); geti_g(geti128, Int128); geti_g(getu128, UInt128) def geti32; geti; end; def getu32; getu; end def write_byte(b : UInt8) : Nil flush if @optr == @oend; @optr.value = b; @optr += 1 end def write(s : String) : Nil size = s.bytesize z = s.to_unsafe i = 0 flush if @oend == @optr while @oend - @optr <= size - i len = @oend - @optr LibIOset.memcpy(@optr.as(Void*), (z + i).as(Void*), len) i += len @optr = @oend flush end if 0 < size - i LibIOset.memcpy(@optr.as(Void*), (z + i).as(Void*), size - i) @optr += size - i end end macro wi_core_g(bit) @[AlwaysInline] private def write_int_core{{bit.id}}(n1 : UInt{{bit.id}}, optr : UInt8*) : Nil if n1 == 0 optr.value = 48u8 @optr = optr + 1 return end t_idx = 0 while 10000 <= n1 n0 = n1 // 10000 REV[t_idx] = OT[n1 - n0 * 10000] n1 = n0 t_idx += 1 end n = n1.to_i16 if 1000 <= n optr.as(UInt32*).value = OT[n] optr += 4 elsif 100 <= n v = OT[n] optr[0] = (v >> 8).to_u8! optr[1] = (v >> 16).to_u8! optr[2] = (v >> 24).to_u8! optr += 3 elsif 10 <= n v = OT[n] optr[0] = (v >> 16).to_u8! optr[1] = (v >> 24).to_u8! optr += 2 else optr.value = 48u8 + n optr += 1 end while 0 < t_idx optr.as(UInt32*).value = REV[t_idx -= 1] optr += 4 end @optr = optr end end wi_core_g(8); wi_core_g(16); wi_core_g(32); wi_core_g(64); wi_core_g(128) macro write_int_g(bit) def write_int(x : Int{{bit.id}}) : Nil flush if @optr + 25 > @oend optr = @optr if x < 0 optr.value = 45u8; optr += 1 write_int_core{{bit.id}} ~x.unsafe_as(UInt{{bit.id}}) &+ 1, optr else write_int_core{{bit.id}} x.unsafe_as(UInt{{bit.id}}), optr end end def write_int(x : UInt{{bit.id}}) : Nil flush if @optr + 25 > @oend write_int_core{{bit.id}} x, @optr end end write_int_g(8); write_int_g(16); write_int_g(32); write_int_g(64) def write_int(x : Int128) : Nil flush if @optr + 45 > @oend optr = @optr if x < 0 optr.value = 45u8; optr += 1 write_int_core128 ~x.unsafe_as(UInt128) &+ 1, optr else write_int_core128 x.unsafe_as(UInt128), optr end end def write_int(x : UInt128) : Nil flush if @optr + 45 > @oend write_int_core128 x, @optr end def write_int(x : BigInt) : Nil; write x.to_s; end def setprecision(x) : Nil raise ArgumentError.new("precision shold be greater than 0 and less than 17") if x < 0 || 16 < x @precision = {x.to_i, 16}.min end def write_float(x : Float) : Nil flush if @optr + 50 > @oend if x < 0 @optr.value = 45u8 @optr += 1 x = -x end prec = @precision write_int x.to_i64 return if prec == 0 optr = @optr optr.value = 46_u8 optr += 1 f = ((x - x.to_i64) * POW10.unsafe_fetch(prec)).to_i64 cur = optr + prec while 4 <= cur - optr f0 = f // 10000 rem = (f - f0 * 10000).to_i f = f0 cur -= 4 cur.as(UInt32*).value = OT[rem] end while optr < cur cur -= 1 f0 = f // 10 cur.value = (f - f0 * 10).to_u8 + 48u8 f = f0 end @optr = optr + prec end def flush : Nil return if @optr == @obuf size = @optr - @obuf LibIOset.write 1, @obuf.as(Void*), size.to_u64 @optr = @obuf end def putv(x : Array(Array(T))) : Nil forall T return if x.empty? putv x.unsafe_fetch 0 (1...x.size).each { |i| write_byte 10u8; putv x.unsafe_fetch i } end def putv(x : Array(Tuple)) : Nil return if x.empty? putv x.unsafe_fetch 0 (1...x.size).each { |i| write_byte 10u8; putv x.unsafe_fetch i } end def putv(x : Int) : Nil; write_int x; end def putv(x : Char) : Nil; write_byte x.ord.to_u8; end def putv(x : Float) : Nil; write_float x; end def putv(x : String) : Nil; write x; end def putv(x : Bool) : Nil; write_byte x ? 49u8 : 48u8; end def putv(x : Indexable(T)) : Nil forall T return if x.empty? putv x.unsafe_fetch 0 (1...x.size).each { |i| write_byte 32u8; putv x.unsafe_fetch i } end def print(*x) : Nil x.each { |v| putv v } end def outl(*x, sep : (String | Char) = ' ', endl : (String | Char) = '\n') : Nil if f = x.first? putv f (1...x.size).each { |i| putv sep; putv x.unsafe_fetch i } end putv endl end end IOSETi = IOset.new @[AlwaysInline]; def ios; IOSETi; end at_exit { ios.flush } h, w = ios.geti, ios.getu sum = 0u32 s = Pointer(UInt32).malloc(h) { x = 0u32 w.times do x &+= ios.getu end sum &+= x x } h.times do |i| ios.outl s[i] &+ sum end