Submission #60878934
Source Code Expand
/*
!!. $# '! -"!
`'.! !!!. '!!! ! `-(- -!. !. !' +#*! -!$%. !(!! `""' -""!`.!$%. '"*. $# .! .!I!! !!!!' 3!(!! .!` ! .!! `!! !.
!!"I .(#%' !"$! '!.! `!&! `%""!! !!!! !j((.'!I"' !! .'! !!' -!I"' `! %B ! -+$(- `'I!' `%!*(. `!(. `!!! !!" .!
.'` .+!('`!tj! '-!!` .`.!. `"!! .!"!.`%$$. !."- .!!( !(' `%$$. !( J@ ! !!.. !! !!`!! '!'.` !. .' "
.!(`'3!".`%##* -!! ."%' `!!*' !!!! !3 !3#"! "!3' .!!` !"!" !3#"! !! "M` ! -+""! !3!+ !"(!! `-"(! `!!!" !*"!` !!
.` ! ! !!! . .!!! ' ! '!` !.` '!!. '` !!. !.(` .!! "M. ! !"! `!!!" "!" . .!! !!! !!" "
!$! `!'! ".3- '(&' '"#(``!#!.!. .!"` !I"!` !!' '%. .(** `"!$. .!(. +M' !- ! `!!(!` ! !! '!!! !'
!!. - !!(' ! .!'! `!'!.-! !! !` ` ' `'` `! (M! .". " !(3 t .!(! ."! !'
"!! !(!` -$(` `!` `!(+ `(%!.! -! " ` `!!! *!` .!(` !3! !M! !' ! !!` ! .' !! !' !
!!. !! '!' .'' `!' `!I!`.! `. '!` ' `' !! !M! '' `!3"!. !!.! !(!! !"!!' !
."'' .". !(!! !!"! .!"! !J! `! !! ! `!. !$` `!*` !!! !M! ``' '! "!!' !!. ``!!. !!u!` .!
'%`(` ("" !'! !!%" !3 ."t"' (` ! -!! `. ' !' !' !M! `..` !`'!! '!!` ' '! ' '!
!.` . '` .! !.` !!!` ! ('%` u 'M+ ..` `!' ..`-!! I "` !(! !!!
!I"!` `!!! !j` 't". !I"!` "!` !. (!". ! `!!M" .' `!!!...!"' ! !` !. !!.
! .!!` ! -'!! ` !! ! `.'!'- .'''...-'!!!!!!! Mu .'.'(!!!(((!"" .``*!' .!+$!!..!!-
`(!. '( "! `!. `!#'` !(!!!!u!!!!!!!$3$$"!!!!..'('!!'.'!!!!!.!%3+"` B% `!*"!!!!!!!3! -''!'! '!"%$"$%%%$$$$$$$$$%$$$"` !!
- !! '! ! .(` `! ! #u%"'.' ( '!..#$"$. #$ .!tI3%z""(*(!"""(!!!(!+"!!!!!! .!$$%%%33%%$%%%%%%$%%%$$$%$"" "$.
`!*! .+3 !$ `""!! !! $%%"!'` !. .!J$$%( ## I"++"*!. .` '"(("!((!!*j!. '+""J&%&"3I%&%%%"j*"u%zu$$%$$j$%"!`
!' .`.. .((. !! `+ 3u"`'. - !' '` !$$%$ $# '+!!"I!! .. `!(!(!+""!"u"- `%3%%%I'!%%%%!(%%%333"$33$3$u%%%'.!%!
.!%! !(!! '!3! " !! !' ''!!`! -(..` ($%$ 3M '!!!+*!! `- !t"""!+"j%3!. "$%%%I "%%%z '"%%%%$$%$$$$I"%%".'j!
'( !! !! !- ' `!'. !! "!! (!`!``.`!!$$$! "M. !!(+I(!. `!'`.(%""*!"3!`! . '#%%%" .` .z%%%!..!(u%$$%%#%$$"j33!!
`"'! !!` '! `(t.` !' .'!'*!! '"!!' `"%#3!` !M! `!"""!! ``` ``'...!"$3zJ%"3"! "$%%".'. !3%%%. `` -*$&($$$$$"%t+
'j!u` .*+` ! ." .!' !`! `! `.!!!! I&%3 'M( !*!"!!` .. !%$##$I"!!"""3(""` u#%%(t$$3! !3%$####! `$(''$$$$$%%$
.! !. '!` '! `!'-.'!!. .'!(!! ! !!j$! `MI `*"!+!!!I##$$ '""*!!.'(!"u((!".!#%%" `!j%%+ ` $!.!%%$%#%%$!
. " .( '!' '! `!'!""! .(!!! ! !"(%" B$ '!+!!"*(`!I"*` .!!"(+++(!!"!(#%%$ '!!!"%%" $u3%%%$%$$%$j
$$""(!!. . ` !!'` !! '! !!' `!!` (` '+""u'! ## `""!(**' ` `!!("!!(.'!+ +#%$$"` !..!.!3%".!z$$%%%%%3%$%$$.
%$$$%%%$$$$$$%%3!!!!!!!!(.!!!!!!` `!! .'!!. `` "!`!"$3!!'! $B !++"(""!!. ..`. `''''.'(!((('!`$$%$$%&!! ` .- .!"%$$%$$$$%%%%%$%$$!
%$#%%%%$u3%%%$%%J. !I!! ($"(I%*!- .-'' .%$$$$%'!.!!! "M` !+""(!!"+!''''''-.''!!+!(!!'!!!.(!*!!%$$$$%$$$$"!!!+!'.-"%$$$%%$%%3&%%$$$(
"J#("""$!(*j%!t%%%' "%$("z$..!!! . '!!(!!!`I!!(.!!' !M! `"""!!!!*"'!!!!!!'! .!!`'*! `` *!!!%%%$#$$3"(+*(('!!` !*"%$$$%%33%%$%$*
("#"33%$3%%%! `z%%$' !! !!!'!!..!!!!!!. '!!!! !."!!.` 'M! `!*(*!!+3*!!!!... ' .`' %.- "*!"$%%%J"(*+(!!!!!!"- `'.(((!I$$%%u%%$%$!
%%#%%%%#%%%" .%%$%. `! .!(!!!!!!''.!.!! !!`!-.! `M" ."!!(!!+"*' `.'!' *!'..` .."!!u%%$$$#"!!!(! !"*!"'. -+!!I3j#%$3%%%$$%
%%#%%%%#%%u`..` *$%$" '!' !!!.!!"`! !'!' !!.+ 3 -`!- B$`!!!!!!"!!*!- . `..'z!!''' !(*%$%$$$#$(!(. `"+"!` !!"$#$%$$#$%%%$#%!
%%#%%%%#%3` .`- $%$% !!!``!'(!!( '!"("!''!+!!!!. `-` ##!`!""!!"!"!!+.. -!!'! - "-' .."$J%$$%$!""' !(!( ("($$$#%%$##%%$#%%!
%%$$%%%#3` !uJ$$!!%%$ ``"!.!.`.j! !!+(! . !!J ! `..`$#!.!""!"(!"!". .'!.``! !'. ' !$'$$%%%I$! "!!! ##$%%$%%%%$#$%%#%%%!
%33#%%%$ (!`!!%% -*-'!'!! # !""*( !" "''.` !3M`(("*!"(!"!!' . ' !!! '` *(#%$$%$! !*!!! !!"$$%%$%%%%%%#$$$%$%%%.
*-'"%%%% !!! !I!` ''-` ' '!'` ! # !"!!I $! " .` jM.`!*(!(+!"(.! !". . ' ".' `.! !$%$$$%$ "!!(! '!#%%%%$%%%%%%%$%$$$$%$"
"` !$%%# ' ! .!..!'. ! # J!!!"! #. !! `!'` .(M' !!+!*"! ! '.-'..! ' ' ".!%"!``!'"(("$$$' !*!!!! #%%%#%$%%%%%%$%%$$%%"$
$! .J%%$!``` ! !....''` `-.!.$ !!!!!!+ `B !!' .!'(M! .*!!!"* !``!.-.- ' ' (.! .`.'!!!!IjJ!! +!!!!+ #%$$#%((!(++*"$%%#%%!!.
%%"'!$%%" ! ! `!!......''` .!!'!!% ."!!!!!" !# !'!!!!'..!M! !"!!!(`! ...!!!`! ! ' ! '!! `' !. .+". ."!!!!" .3"""%"(!!!!!!!"%%#%$!.
%%%%$#$%#` '.`! !.'!!'....'!'...!!I !!!!!!!! "J !!!!.....!M! (`!!!! ! ' !.!*( ' ! ".! .`'' ` ! !!!!!!" '. .' *$""%$$$z
%%%%%$#$$I ! !....''.....!!!'!!" !!!!"! 3!`'!!........!M! !` `!' ' .....- ! ! ".! ! '` ! "!!!!!+ !. !*"""z%$$$. !$%%$!
%%%%%$%$%$! !. !!........!!..` '!!". .!!+'- `'!.`` `........'M! ! `' ! .` !'! ' ! ! ``.(!!!!!! !` ! .%"!!$%%%$.
%%%%%$%%$$#!''!!!!!3"!((*+"""""""""""""j%uuJJJJzzz33$3j3uuuz$#$$$$$$%$$$$$$$$$#########B########################################################Q#####$$$$#$$$$%%%$#########"+*
######$$###$I######$$3"(!!(((!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'''''!-...'.--` '! !! !I""!"j .'.!!!!( ```.!!!!!.-''!'!!!!!!!!!!!!
!!"3$$$$3 $%%%%%%%$$$$$$3"3(!!. .'. `.'.`` `. ` .!!'. `!.!! .u"+%%%("j .` . !(`" `t####$! !B"#$j'
I$%%%%%%%%! !%%%%%%%%$%%%%%%$%$$j"(!!' `'!' `'!'. .. .t""""3u(! `'''''''!!!!!!!!!!.j(Iz"+"%(u! ''!! !####& *z#!*#+
%%%%%%%%%$' "%%%%%%%%$%%%%%$%%%%%%#$('!!!` `!!' ... .. !!%%%%I"""I"''. !*$""!3+"%!$` `'!'.`" (##### B!.`
""*!!$%%%$ $%%%%%%%%$%%%%$%%%%%%%%%$$! .'''` `!!' ` !!%u"""""!' -!! `%(JJ!" ''" .!...! !''!
`$%%%u !$%%%%%%%%$%%%$%%%%%%%%%%%%%&! .''' `!!' !!%""' -` ` !!!%(%!$` ''(` !I""$! '@&##3.
%" !%%$3! (%%%%%%%%%$%%$$%%%%%%%%%%%%%%$! ...` `'-. !!3I(!' `. `` '""%""! `! '! `'!#( B+## $"
%! !!- I%%%%%%%%%$%%$%%%%%%%%%%%%%%%%$! ` .`` .$(%!! .` . ` .`!.` ` '` 'u3!( .!- `* `!!` *%("$"`
` !!!("j%%%%%%%%%%%$%$$%%%%$%%%%%%%%%$%%$' $!%" .` `'````..`+ !`.`.'`! %"" !!.I!!" !!!!!(- `!".'`
% !%%%%%%%%%%%%%%%%%$%$%%%%%$%%%%%%%%$%%%%& (!u` `.`...`..'``! ` (' `!` !'.+...!`` !$%I!.` !+.. !!j#"!` "M"!#j!
" $%%%%%%%%%%%%%%%%%$%$%%%%%$%%%%%%%%$%%%%$! 3!```!`'.` ' '! ! "` . ''` (`!'``!...`3%%%".!*." #"` #u3"M".
! !%%%%%%%%%%%%%%%%%"j$3"%%%$I"%%%%%u`+%"I%$$ !..`!`! ' .' (`.!.!.`.` !! ." ! !`` "%#! `. !. .(u! ``3tj!'
3%%%%%%%%%%%%%%%%"!j#!""3%$!"%%%$" .$u!"%u! !*`` !-! ! ! ' .!! !!` ` .!! (!! ! "%$' ! ""#$ `!!!!
.$%%%%%%%%%%%&3"(j!!%$(z%%%$t%%%$* "%Iu%$% !%!. `'!' !`*' !.! '! .. !-` .+! -.!$%%$ ! ! ."##"! !!!!#"
!%%%%%%%%%%"j""**"!t%#3%%%$$%%%$! !$%%%$%! `!! !!' '!"'!`.!' ' `'!!!!` `-`!' (%u($%!`'. ! !%$$!B- .j3u.
$%%%%%%%%%%%%%%%%%""%##%%%%#%%$3. ...` !"%%%$%" '( !(' ! !%+"!`.' -`` `!"$#"("" - !("!(%$ '!` !` .!(!.
%%%%%%%%%%%%%%%%%%%%$#$%%%%#%$! !-$%%%$% !! !!'.!%+3##3!.' '!` .B#$"$ ! . !3%$'$$.`!!' '! zuJ###! juJ##%!
%%%%%%%%%%%%%%%%%%%%#$$%%%%#(` '!!'! 3%%%$$` '! `!'!!` $%%$3. '.` $"""$ ' ` ` $%%-$$'!!'+ .! #".(! #"
%%%%%%%%%%%%%%%%%%$I$#%%%%%" `"#BBBB% !$%%$%. !! ! +` !I""! `..-.` !!(. ' ! ' "!!u%!.!!.!``! I#3! "#%!
%%%%%%%%%%%%%%%%%%*!!z%%%%%( !#! #!!" `#%%$$` -'' !'!! `!` !.! ! 3$$"...!-! *` !`
%%%%%%%%%%%%%%%%%$!`'3%%%%%" ! $!u! $%%$" .! ' !!'-! .-'''!` ! !!! `! ""!'...! ! ( .M`
%%%%%%%%%%%%%%%%%%!. u$%%%%" $!". I%$$. `! '` ! !'!'! ("!''.'. !"(!"!`'`!'..!...! . * .M .#`
%%%%%%%%%%%%%%%%%#% ($%%%%u !!". `.!%$' ` '' !.!.!..!'. `!````.` !!!!(%%$#$$$$"..!!..! !` $$3$!
%%%%%%%%%%%%%%%%%## !!%%%%%% . `!I- .!!! !. .!%"!!!....!'''''. `!!! "!3""*$$#!..!!.! `!'!! !'
%%%%%%%%%%%%%%%%%$$" !I%%%%$ ! ! `!+uz%$$%( +.!........-!!(!! ''` !! !`!...!.!!- `!!` "#".
%%%%%%%%%%%%$%%%%$$"!`($%%%$.. .' .' `"%$#!!!"'-!!!!.'......''.'3 '! ! ' !!!!! " !%##". . !
%%%%%%%%%%%%$$%%%$$. !%%%%%!-` ! . .u"' .` !! !!!!!!!.!!!! ."!' !`` !(#!!!` !! .((.. `" !!.*
%%%%%%%%%%%$$$%%%$" !($%%%! .. '! `' ' ' ' ' !!"+` ! !''!! .-!. `!$".! !' !! !u "! "! "!!(
%%%%%%%%%%%$$$%%%$! ! #%%%! ! .. !! !' !! ' ''` "! .!'""+"$! `!!.` .!!#`! ! !! (# #" # % `'
%%%%%%%%%%%$#$%%$$! ''!$%%% '! + !`! +!!` `( "! !!"!!!( !.(`.' !'$! . `! !! !3 "! !$ $
%%%%%%%%%%$ "$%%#%! !`$%%$. !!`. ! !!! "'! `'!. "! !!3%"! ! ' !.!B `!` `" ``!"."! $* .!!#!!!'.
%%%%%%%%%$(-J%%%#%' z!!$%%"!!!.``.!' '. !`! +'! `! ! "! !z!("! ..'- *# . ." ` +!!!!!!!!!!!''''''"'!!#(!! #
%%%%%%%%%% !%%%%$$' ! ! *%%$ ...` ' .. !. ! ! !( !3!!!". ''. $" ! '"( !` `("!' ." #
%%%%%%%%$!!%%%%$"u ''( !. u%$! `` '`.!'!!'!' ` !% "!!!!(! B` ! `!3"! ' . $
%%%%%%%$" u%%%%"%"' .!'`! '%%% ``` ` '.. .!!..-"' ` . '# ."!!!!!"` '# +.` "##` ! ` `!!!!! . `'
%%%%%%%$ "%%%%$.$!`!''' "`. !$%! `!''-.` `'!!!' !..!!! `!. ! @ *!!!!!!!* (" ( `"(!!+!.. '!` `. .u"`
%%%%%%$!($%%%%+'#` '!!!. (%%. .''''-... !!++!' .!!...!! .!( #! "!!!!!!!(' 3! !..`` .(+-..."I!' ! `!!! .II.
%%%%%%"!$%%%%% !j -!%%z.``... .!!"!!` . .'".......!! ..''!' "+ ."!!!!!!!(' #. !(- .!!.......+!! .!('... `I%.
%%%%%3!$%%%%$' u"!!""u3%%%3"('`+$" .- '!!!!! `` `!' '''-........'!! .( '# '"!!!'(%' # I!!!''..........(!!. .. *$!
%%%%%"$%%%%$$z$#$%%%%%%%%%%%%$3! !!!!!!-'`''!!'` ... '!!`` `.!..!!........-!!!!" #. "!!3".' $ '!!!!............'!t"(! `! '#(
%%%%#$%%%%%#%%$$%%%%%%%%%%%%%%%%$! !!!!(!'. `.. -!-.!` '.` .. !!...!!!.......``!!!! "" ! !!'.' -'!!!...............'!"($(("` ! "%`
%%%$$%%%%%$%%%$$%%%%%%%%%%%$$$$$$$$!!!!tu"!!!!!!!(+""**+"""""""%u"$$IIjjuJz$$%%%%3$$$$$$$$##$$$$$%%33z$#j3#""""%"3""+j""""!!!(!!!!!!!!!(((!!!!!+!!!-!"` `! `(!
$$############Q#############$$$$$%%33uI""t""""++*(((((!""!!!!!!!!!!!"!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(((**+"""""""IjJ33%%$$$$$$$###################$$$%3Jt""+(!!
*(!!!!!!''.` ! `! '` ' ``.'!!!!!'...' ``` `..''!!!!!!!!!(
.. "%!! ! !'. !-.-'.'`!..! ' '.'!`-
! !'*` .. '` `.''.``` '!"3! !`! `! ..!!!!!`
`' .#3$( ! ..!-.` ' ...'!. !3"!(!$! -!! `(!(!!!!'..-!
! `!!!' ! 'u""!!!!.-''''. `.!. !%"!"%3z!$! '.` !`!!*j$$$%%$$$$#$uI"!
`-'''''.! !$! ! '*(*+***Iz"!` .!!'!!!'!!'`!3!"t(+((J!$`...`.` !"$$$$$$$$$$$$$$$%$$$$&!`
!'` ! .!!. ! `!"!%%&uJj"*(3!''` .!!!(I""!+"**"" -'!``($$$%%%%%%%%%%%%%%%$$$$$$%%!
'' ! !!' ! ''*!%%!"""""!` '!! &!"!$ !$%%%%%%%$%%%%%%%%%%%%%%%$$$$%j' `!""' .
! ! -!. -' -'(!3%!!`!. !!$!!$! '%%%%%%%%%%$%%%%%%%%%%%%%%%%%$$$%$!!%%$$+ !"
'! ! `! ! ! -'!""%!". !3!3"!%%%%%%%%%$u3"%%%%%%%%%%%%$%%%%%$#$$%$$%$$ "%!
`` .!"%%$! ! ` ` !` +!!. !!!. $!%%- ` ` .I$I**J3"+*%$3! !("3%%%3%%%%%33$"""I%$%%$$$%%$$"("$"`
`.''.-.`!"$%%%%%$. !. .!- ((!. ! ! `!-..-!"!$! ' ' `! j$J3%%%3$$! !tu%%%%'%%%%%t"u"*""%$$$%$%""%$(%"!
!%$%%%%%%%%" ! !!. !-! -! ! ! .*j! `' .''. . ` -!```` "%%%%%%$$' %$%%%$`.u%%%%%%$%$%$$%$%%$+"""* !&%!
-3$%%%%%%%%%%#.. ' .'!` `!'' !! ' !! !(. `! ` . !!' '' .! `!$%%%%%$3'.. ($%%%$! (%$%%%$%%$%$%%#%%$(""% !$!
!$%%%$$%%%%%%%$! .- ' .' '. .! '-` ."%. ! .. !!! .!' -' !' J%%%%%$( .$$%%%"...!3$$%$%%$%%$%#%%$"z%%! IJ
`I$%%%$$%%%%%%%%%" .' ! '!. !!!` '!- '!' !(*. ' `' '!!' .!!'!!` ! .$%%%%$( `. !$%%%$. !"$$$%$$$$%%#%%$"$%"!!!(.
.3%%%%$$%%%%%%%%%%$ !' '` .""! "! `j- `!' ` !.!``` `!''. '.'!'! !` !%%%%%$!I####J. j$%###$%+' 'z$%$%%%$$$$%$$$%$.
'$%%$$%#%%%%%%%%%%$ `!` ! '!!! ! * "!. `!!' .!(""*! ''! '%%%%%%"''.`` .#%%%$"!"!. ($%3'%$$%%$%%$$%%!` `.
"%$$%%$#%%%%%%%%%$ .!' ! '! ! '' #'' .!.!j###"! !#%$##+z! ! !%%%%$%(!.!. '$%%%%!'!.` &!%3.!$$%%$%%$%$%!! `..!.
!$$%%%%#%%%%%%%%%$ .''! ! !!!! ' ! $'! !!"$#(%$" %"j"# .` ! !%%%$%%"'`. ` '$%%%3.' `!!%%!3%$%%$%%%$%%" ! `!'
"%%%%%#%%%%%%%%%$ ..!..' ' ! ! "!! !.!.$""*I '!!!. '$%%+"%%%$%%$( !.''''!!%%%%%- '%#%%%$%%$%%%%%%$. ! ...
.($%%$%%%%%%%%%$ `.'..!.`. `! ! ( !!. !%" !!!` . 3$3!"%%%#%%%%t! ..``'!''.j%%%I`!"%$%#%%%#%%$%%%%%$%! `'
`(%%%%%%%%%$%' ```!` !... '! `! !'""""3#$%! ` !!! "%%%$%%%$%%$!' .` `."%%%$+"%$%$%%$$$%$%%%%%$%% .`
!(%%%%%$$%"+!` '' ! ..- !!(' ! !.*$$3""("'! ''! !!'.! "%%$3%%$$I"!!!*!!!''''''- '&%%%+!%%$%%$%#%$%%%%%%$%! '
'3%%%%%%%%%$! `! ! .! ! -!' !!.!" !!.!.!'' '. !!""!!!! j%%$"$J"!!!!""+(!!+!! !(%%%t3$"3$$%$%$$%%%%%$%% `.
````` `3%%%%%%%(! `! ! ! !! (' !''-+ '!'!(!*!*(!!!!'.-''(!!!!*(*-.3%%$"!!!!(""!!!!!+ '! !!! !"j%$$"!(%$%$%$%%%%%%$%( '
`...` `%%%%$$` '! ! `. .!..'!!!!!!!!!!! .!!!"` ! !"!!!!!!(I' `. !!"!!!!+" $I"*!!!""!!!!*"!!. '!!. -((*"$%%I"J$%%$%%%%%%$3%' '
.$%%%%u! ( !! ... `!"!!!!!' !`!*!!!!(''!'''`'!` "!!j"( $z"$"*"!!!!!!. `' .!!(! !' (""%"!""t$$%$%$%%%%%""3.'
!$%%%%%&! ! !! `` !!!!!!!!".."!!*!!!! `!!!` t!!*.'$$3#$"(!!!!! -!!!!+!.' %"$"(""!$$%$%$$%%%%%!"$-
!$%%%%%%%j` ! ! '! !!!!!!!!"+'.++"!. .' ((+""! !! '!'!$%$z$#"(!!(' `-3""!``` !"$""$$$$$$%$%#%%%%%&!"%!
!%%%%%%%%%j ! !' !!!!!!!!!!((!!` !'!!((("!!!` $%%$I*!**!"' 3(!*' *t$+$##%%%#$$%$$%%%%%u`!%"-
!%%%%%%%%%$. ! ... .! !!(""""(!!!!!!(! -!.""(".''. $$%$$t("3("` %!!!! I"$!"$%%%%%#%$$$$%%%%%" `(%"!`
!%%%%%%%%%! ! ! ` "!!!!!!!""t(!!!!(! .` ."!!+!. !$#%$%%u3##u !+!!!! `I"#"$%%%%%%#$$$$%$%%%%$! ...
!%%%%%%%%* !` ! !!!!!!!!!!!"t"!!!(! !!!!!" %$#%$%%%%"$$ I!!(!!. !"##$%%%%%%%%#%$$$%$%%%%$
.#%%%%%%" '..`! !"*!!!!!!!!!!"+(!!!! !!!!!*! !*%3$%$%%%%""` `3!!!!(. `'!!+"$$$%%%%%%%%$$%$$%%$%%%%+
. !$$%%+! *.! ! `j3*!!!!!!!!!!!!!!(!. (!!!!!j !!"$%%%(**+j"! !(!!!!". J""+I"$$$%%%$%I""($%%$$%$$%%%$!
`' .!'!.'' %+"&! '-'! ($$$%jI""!!!!!!!!!"I! "!!!!!!+ -.!!!'!3 !&"!"%z"! "!!!!!!! !"!$"!!!!!!*""I%#%%%%%$%%$%&`
.. !'.!*""$(+j$%%$! .- !'''` $$$$$$$$$$%3"(!!!!!!(+!"!!(!!'!'` !' .!! `!` (! 3!!!!!!" "' "J%"!!'..` $%%%%%$%%$%%!
.. .!!.%%%$#$$#$$%% .!!!!.!!! !` !$$$$$$$$$$$$$$3(!!!!!!*++! !. ( !! '+ 3!!!!!!I ( !` !$%%%%$%$%%%%
*/
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#ifdef ATCODER
#include<boost/heap/d_ary_heap.hpp>
#include <atcoder/all>
#include <random>
#include <boost/multiprecision/gmp.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/dynamic_bitset.hpp>
#define cpp_int mpz_int
#endif
#ifdef _MSC_VER
#define _SILENCE_ALL_CXX23_DEPRECATION_WARNINGS
#include<boost/heap/d_ary_heap.hpp>
#include <atcoder/all>
#include <random>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/dynamic_bitset.hpp>
#endif
#include <random>
#include <chrono>
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
//#pragma GCC target("avx,avx2,avx512f,avx512vl,avx512bw,avx512dq,sse,sse2,sse3,ssse3,sse4.1,sse4.2,bmi,bmi2,abm,fma")
using namespace std;
using namespace std::chrono;
#ifdef ATCODER
using namespace atcoder;
using namespace boost::multiprecision;
#endif
#ifdef _MSC_VER
using namespace atcoder;
using namespace boost::multiprecision;
inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; }
inline unsigned int __builtin_ctz(unsigned int n) { unsigned long r; _BitScanForward(&r, n); return r; }
#endif
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define repi(i,a) for (auto i = (a).begin(); i!=(a).end(); ++i)
#define repa(i, n) for (int i = 1; i <= (int)(n); ++i)
#define reps(i,a, n) for (int i = (a); i < (int)(n); ++i)
#define repm(i,a) for (int i = ((a)-1); i >= 0; --i)
#define repbit(i, n) for (int i = 0; i < (1LL<<(n)); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ul = unsigned long long; using ll = long long; using ld = long double;
//#define BIT fenwick_tree
#define endl '\n'
constexpr const long long INF = (1ll << 62);
constexpr const long double PI = 3.141592653589793238462643383279502884;
constexpr const int INFi = 1LL << 30;
//template<class T, class U>inline bool chmin(T& a, const U& b) {
// if (a > b) {
// a = b; return true;//更新が発生した=trueを返す
// }
// return false;
//}
#define chmax(a,b) ((a)<(b)?(a)=(b),true:false)
#define chmin(a,b) ((b)<(a)?(a)=(b),true:false)
#ifdef YAJU&U
struct Scanner {
char* buf;
long wt, rd;
size_t maxsz;
public:
Scanner(int size = 1 << 12) : maxsz(size) {
buf = (char*)malloc(sizeof(char) * size);
_read();
}
std::string read_str() {
int ch = _chr();
while (isspace(ch)) ch = nxchar();
int rd_first = rd;
std::string res;
while (rd <= wt && !isspace(buf[rd])) {
++rd;
if (rd == wt) {
res += std::string(buf, rd_first, wt - rd_first);
_read();
rd_first = 0;
}
}
res += std::string(buf, rd_first, rd - rd_first);
return res;
}
char read_chr() {
int ch = _chr();
while (isspace(ch)) ch = nxchar();
return ch;
}
template<class T> T read_int() {
T ret = 0;
bool s = true;
int ch = _chr();
while (isspace(ch)) ch = nxchar();
if (ch == '-') {
s = false;
ch = nxchar();
}
for (; isdigit(ch); ch = nxchar()) ret = ret * 10 + ch - '0';
return (s ? ret : -ret);
}
template<class T> T read_flt() {
return stold(read_str());
}
std::string read_line() {
int ch = _chr();
while (isspace(ch)) ch = nxchar();
int rd_first = rd;
std::string res;
while (rd <= wt && buf[rd] != '\n') {
++rd;
if (rd == wt) {
res += std::string(buf, rd_first, wt - rd_first);
_read();
rd_first = 0;
}
}
res += std::string(buf, rd_first, rd - rd_first);
return res;
}
private:
void _read() {
long r = read(0, buf, maxsz);
if (r < 0) {
throw std::runtime_error(strerror(errno));
}
wt = r;
rd = 0;
}
inline int nxchar() {
++rd;
if (rd == wt) _read();
return _chr();
}
inline int _chr() {
return rd == wt ? EOF : buf[rd];
}
} sc;
inline short Short() { return sc.read_int<short>(); }
inline unsigned short UShort() { return sc.read_int<unsigned short>(); }
inline int Int() { return sc.read_int<int>(); }
inline unsigned int UInt() { return sc.read_int<unsigned int>(); }
inline long Long() { return sc.read_int<long>(); }
inline unsigned long ULong() { return sc.read_int<unsigned long>(); }
inline long long LLong() { return sc.read_int<long long>(); }
inline unsigned long long ULLong() { return sc.read_int<unsigned long long>(); }
inline float Float() { return sc.read_flt<float>(); }
inline double Double() { return sc.read_flt<double>(); }
inline long double LDouble() { return sc.read_flt<long double>(); }
inline std::string String() { return sc.read_str(); }
inline char Char() { return sc.read_chr(); }
inline bool Bool() { return sc.read_chr() == '1'; }
inline void _SingleInput(short& n) { n = Short(); }
inline void _SingleInput(unsigned short& n) { n = UShort(); }
inline void _SingleInput(int& n) { n = Int(); }
inline void _SingleInput(unsigned int& n) { n = UInt(); }
inline void _SingleInput(long& n) { n = Long(); }
inline void _SingleInput(unsigned long& n) { n = ULong(); }
inline void _SingleInput(long long& n) { n = LLong(); }
inline void _SingleInput(unsigned long long& n) { n = ULLong(); }
inline void _SingleInput(float& d) { d = Float(); }
inline void _SingleInput(double& d) { d = Double(); }
inline void _SingleInput(long double& d) { d = LDouble(); }
inline void _SingleInput(std::string& s) { s = String(); }
inline void _SingleInput(char& c) { c = Char(); }
inline void _SingleInput(bool& b) { b = Bool(); }
template<class S, class T> inline void _SingleInput(std::pair<S, T>& p) { _SingleInput(p.first); _SingleInput(p.second); }
template<class T> inline void _SingleInput(std::vector<T>& v) { for (T& x : v) _SingleInput(x); }
void input() { }
template<class T1, class... T2> void input(T1& t1, T2&... t2) { _SingleInput(t1); input(t2...); }
template<typename T> inline void print_int(T n) {
if (n < 0) {
putchar_unlocked('-');
n = -n;
}
if (n < 10) {
putchar_unlocked('0' + n);
return;
}
int i;
char b[21];
b[20] = 0;
for (i = 20; n > 0; b[--i] = '0' + n % 10, n /= 10); fputs(b + i, stdout);
}
template<typename T> void print_bigint(T n) {
if (n < 0) {
putchar_unlocked('-');
n = -n;
}
if (n < 10) {
putchar_unlocked('0' + n);
return;
}
int i;
char b[41];
b[40] = 0;
for (i = 40; n > 0; b[--i] = '0' + n % 10, n /= 10); fputs(b + i, stdout);
}
void print_char(char c) {
putchar_unlocked(c);
}
void print_string(std::string s) {
for (char& c : s) {
putchar_unlocked(c);
}
}
template<typename T> void print_double(T d) {
print_string(std::to_string(d));
}
inline void _SingleOutput(short n) { print_int<short>(n); }
inline void _SingleOutput(unsigned short n) { print_int<unsigned short>(n); }
inline void _SingleOutput(int n) { print_int<int>(n); }
inline void _SingleOutput(unsigned int n) { print_int<unsigned int>(n); }
inline void _SingleOutput(long n) { print_int<long>(n); }
inline void _SingleOutput(unsigned long n) { print_int<unsigned long>(n); }
inline void _SingleOutput(long long n) { print_int<long long>(n); }
inline void _SingleOutput(unsigned long long n) { print_int<unsigned long long>(n); }
inline void _SingleOutput(float d) { print_double<float>(d); }
inline void _SingleOutput(double d) { print_double<double>(d); }
inline void _SingleOutput(long double d) { print_double<long double>(d); }
inline void _SingleOutput(std::string s) { print_string(s); }
inline void _SingleOutput(char c) { putchar_unlocked(c); }
inline void _SingleOutput(bool b) { putchar_unlocked(b ? '1' : '0'); }
template<class S, class T> inline void _SingleOutput(std::pair<S, T> p) { _SingleOutput(p.first); putchar_unlocked(' '); _SingleOutput(p.second); }
void print() { putchar_unlocked('\n'); }
template<class T> inline void _SingleOutput(std::vector<T> v) { for (int i = 0; i < v.size() - 1; i++) { _SingleOutput(v[i]); putchar_unlocked(' '); } _SingleOutput(v.back()); }
template<class T1, class... T2> void print(T1 t1, T2... t2) { _SingleOutput(t1); print(t2...); }
#endif // !_MSC_VER
//template<class T, class U>inline bool chmax(T& a, const U& b) {
// if (a < b) {
// a = b; return true;//更新が発生した=trueを返す
// }
// return false;
//}
//返り値(負の閉路を持つかどうかを示すフラグ、最短路帳が格納されたvector)
struct Edge {
int to;
ll w;
};
#define Graph vector<vector<Edge>>
/*
class Graph {
public:
Graph(int n) {
G.resize(n);
UF.resize(n);
}
inline int size() const {
return G.size();
}
inline vector<Edge> operator [](const int& t)const {
return G[t];
}
inline vector<Edge> operator [](const int& t) {
return G[t];
}
inline void add_edge(const int& e,const int& to,const int& cost=1) {
G[e].emplace_back(to);
}
private:
vector<vector<Edge>>G;
struct UnionFind {
public:
UnionFind() : _n(0) {}
explicit UnionFind(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
void resize(int n) {
parent_or_size.resize(n, -1);
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
UnionFind UF;
};
*/
inline pair<bool, vector<long long>> BellmanFord(const Graph& G, const int& s) {
int N = G.size();
bool exist_negative_cycle = false;//負の閉路を持つかどうか返す結果を初期化
vector<long long> dist(N, INF);
dist[s] = 0;
for (int i = 0; i < N; ++i) {
bool update = false; // 今回の(すべての)辺の緩和で更新が発⽣したかどうか
for (int v = 0; v < N; ++v) {
if (dist[v] == INF) continue;
for (auto e : G[v]) {
if (chmin(dist[e.to], dist[v] + e.w)) {
update = true;
}
}
}
if (!update) break; // 更新が発⽣しないならばすでに真の最短路⻑が求まっている
if (i == N - 1 && update) exist_negative_cycle = true; // 負の閉路がある場合
}
return pair<bool, vector<long long>>(exist_negative_cycle, dist);
}
inline vector<ll> Dijkstra(const Graph& G, const vector<int>& s) {
int N = G.size();
struct litepair {
ll first;
int second;
inline bool operator<(const litepair& lt)const {
return lt.first < this->first;
}
};
vector<long long> dist(N, INF);
#ifdef BOOST_VERSION
boost::heap::d_ary_heap <litepair, boost::heap::arity <5>>que;
#else
priority_queue<litepair>que;
#endif
for (int i = 0; i < s.size(); ++i) {
dist[s[i]] = 0;
que.emplace(0LL, s[i]);
}
while (!que.empty()) {
auto [d, v] = que.top();
que.pop();
if (dist[v] < d)continue;
for (int i = 0; i < G[v].size(); ++i) {
if (chmin(dist[G[v][i].to], dist[v] + G[v][i].w)) {
que.emplace(dist[G[v][i].to], G[v][i].to);
}
}
}
return dist;
}
inline vector<vector<ll>> Dijkstra_all(const Graph& G) {
int N = G.size();
struct litepair {
long long first;
int second;
inline bool operator<(const litepair& lt)const {
return lt.first < this->first;
}
};
#ifdef BOOST_VERSION
boost::heap::d_ary_heap <litepair, boost::heap::arity <5>>que;
#else
priority_queue<litepair>que;
#endif
vector<vector<long long>>dist(N, vector<long long>(N,INF));
for (int i = 0; i < N - 1; ++i) {
dist[i][i] = 0;
que.emplace(0LL, i);
while (!que.empty()) {
auto [d, v] = que.top();
que.pop();
if (dist[i][v] < d)continue;
for (int j = 0; j < G[v].size(); ++j) {
if (chmin(dist[i][G[v][j].to], dist[i][v] + G[v][j].w)) {
que.emplace(dist[i][G[v][j].to], G[v][j].to);
}
}
}
for (int j = i + 1; j < N - 1; ++j) {
dist[j][i] = dist[i][j] + 1;
}
}
for (int i = 0; i < N; ++i) {
dist[N-1][i] = dist[i][N-1];
}
return dist;
}
inline pair<vector<ll>, vector<int>> Dijkstra_root(const Graph& G, const int& s) {
int N = G.size();
struct litepair {
ll first;
int second;
inline bool operator<(const litepair& lt)const {
return lt.first < this->first;
}
};
vector<long long> dist(N, INF);
vector<int>fukugen(N);
#ifdef BOOST_VERSION
boost::heap::d_ary_heap <litepair, boost::heap::arity <5>>que;
#else
priority_queue<litepair>que;
#endif
dist[s] = 0;
que.emplace(0LL, s);
while (!que.empty()) {
auto [d, v] = que.top();
que.pop();
if (dist[v] < d)continue;
for (int i = 0, size = G[v].size(); i < size; ++i) {
if (chmin(dist[G[v][i].to], dist[v] + G[v][i].w))
fukugen[G[v][i].to] = v,
que.emplace(dist[G[v][i].to], G[v][i].to);
}
}
return make_pair(dist, fukugen);
}
template <class T>
inline vector<int> BFS(const vector<vector<T>>& G, const int& s) {
int N = G.size();
vector<int> dist(N, -1);
queue<int> que;
que.emplace(s);
dist[s] = 0;
while (!que.empty()) {
int v = que.front();
que.pop();
for (int i = 0; i < G[v].size(); ++i) {
if (dist[G[v][i]] == -1) {
dist[G[v][i]] = dist[v] + 1;
que.emplace(G[v][i]);
}
}
}
return dist;
}
inline vector<int> BFS_on_tree(const Graph& G, const int& s) {
int N = G.size();
vector<int> dist(N, -1);
queue<int> que;
que.emplace(s);
dist[s] = 0;
while (!que.empty()) {
int v = que.front();
que.pop();
for (int i = 0; i < G[v].size(); ++i) {
if (dist[G[v][i].to] == -1) {
dist[G[v][i].to] = dist[v] + G[v][i].w;
que.emplace(G[v][i].to);
}
}
}
return dist;
}
#ifdef BOOST_VERSION
inline istream& operator>>(istream& is, cpp_int& v) {
string t;
is >> t;
v.assign(t);
return is;
}
#endif
template <class T>
inline istream& operator>>(istream& is, vector<T>& v) {
for (auto& x : v)is >> x;
return is;
}
template <class T, class U>
inline istream& operator>>(istream& is, vector<pair<T, U>>& v) {
for (auto& x : v)is >> x.first >> x.second;
return is;
}
template <class T>
inline ostream& operator<<(ostream& os, const vector<T>& v) {
for (int i = 0; i < v.size(); i++)
if (i != (int)v.size() - 1)os << v[i] << endl; else os << v[i];
return os;
}
template <class T>
inline ostream& operator<<(ostream& os, const set<T>& v) {
for (auto i = v.begin(); i != v.end(); ++i) {
if (i != --v.end())cout << *i << endl; else cout << *i;
}
return os;
}
template <class T>
inline istream& operator>>(istream& is, set<T>& s) {
T cinset;
is >> cinset;
s.emplace(cinset);
return is;
}
template <class T, class U>
inline istream& operator>>(istream& is, pair<T, U>& s) {
is >> s.first >> s.second;
return is;
}
template <typename T, typename U>
inline const T abs(const T& a, const U& b) {
if (a - b >= 0)return a - b;
else return b - a;
}
inline vector<int>topsort(const vector<vector<int>>& G) {
vector<int>ans; vector<bool>seen(G.size(), false);
function<void(int)>fortopsort = [&](int v) {
seen[v] = true;
for (int i = 0; i < (int)G[v].size(); i++) {
int w = G[v][i];
if (seen[w]) continue;
fortopsort(w);
}
ans.emplace_back(v);
};
rep(i, (int)G.size())if (!seen[i])fortopsort(i);
reverse(ans.begin(), ans.end());
return ans;
}
inline vector<int>topsort(const Graph& G) {
vector<int>ans; vector<bool>seen(G.size(), false);
stack<int>st;
rep(i, (int)G.size())
if (!seen[i]) {
seen[i] = true;
st.emplace(~i);
st.emplace(i);
while (!st.empty()) {
int v = st.top(); st.pop();
if (v >= 0) {
for (int i = 0; i < (int)G[v].size(); i++) {
int w = G[v][i].to;
if (seen[w]) continue;
seen[w] = true;
st.emplace(~w);
st.emplace(w);
}
}
else {
ans.emplace_back(~v);
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
inline ll DFS(const vector<vector<int>>& G, int v, vector<bool>& seen) {
seen.resize(G.size()); ll ans = 0;
function<void(int)>forDFS = [&](int tov) {
for (int i = 0; i < (int)G[tov].size(); i++) {
int w = G[tov][i];
if (seen[w])continue;
seen[w] = true;
forDFS(w);
}
};
seen[v] = 1;
forDFS(v);
return ans;
}
inline vector<bool>nibgraph(const vector<vector<int>>& G, const int& v = 0) {
vector<bool>ans(G.size());
vector<bool>seen(G.size());
seen[v] = true;
function<void(int, bool)>forDFS = [&](int tov, bool ks) {
if (ks)
ans[tov] = true;
for (int i = 0; i < (int)G[tov].size(); i++) {
int w = G[tov][i];
if (seen[w])
continue;
seen[w] = true;
forDFS(w, !ks);
}
};
forDFS(v, true);
return ans;
}
template<typename T>
inline vector<T> ruisekiwa(const vector<T>& a) {
vector<T>rui(a.size() + 1);
rui[0] = 0;
for (int i = 0; i < a.size(); ++i) {
rui[i + 1] = rui[i] + a[i];
}
return rui;
}
template<typename T>
inline vector<vector<T>> ruisekiwa(const vector<vector<T>>& a) {
vector<vector<T>>rui(a.size() + 1, vector<T>(a[0].size() + 1, 0));
for (int i = 0; i < a.size(); ++i)
for (int j = 0; j < a[0].size(); ++j)
rui[i + 1][j + 1] = rui[i + 1][j] + a[i][j];
for (int i = 0; i < a[0].size(); ++i)
for (int j = 0; j < a.size(); ++j)
rui[j + 1][i + 1] += rui[j][i + 1];
return rui;
}
template<typename T>
inline void ruisekikukankasan(vector<T>& a, int l, int r, int val = 1) {
a[l] += val;
a[r] -= val;
}
template<typename T>
inline T ruisekiat(vector<T>& a, int l, int r) {
return a[r] - a[l];
}
template<typename T>
inline T ruisekiat(vector<vector<T>>& a, int lx, int ly, int rx, int ry) {
return a[rx][ry] - a[rx][ly] - a[lx][ry] + a[lx][ly];
}
//for (int i = 0; i < h; ++i)
//for (int j = 0; j < w; ++j)
//s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + a[i][j];
inline vector<bool>eratos(const ll& kaz) {
vector<bool>isSosu(kaz + 1, true);
isSosu[0] = false; isSosu[1] = false;
for (ll i = 2; i * i <= kaz; ++i) {
if (isSosu[i]) {
for (ll j = i * i; j <= kaz; j += i) {
isSosu[j] = false;
}
}
}
return isSosu;
}
inline string yn(const bool& maj) {
return (maj ? "Yes" : "No");
}
template <typename T>
inline T max(const vector<T>& Vec) {
T ma = Vec[0];
rep(i, Vec.size())chmax(ma, Vec[i]);
return ma;
}
template <typename T>
inline T max(const vector<vector<T>>& Vec) {
T ma = Vec[0][0];
rep(i, Vec.size()) {
rep(j, Vec[i].size()) {
chmax(ma, Vec[i][j]);
}
}
return ma;
}
template <typename T>
inline T min(const vector<T>& Vec) {
T ma = Vec[0];
rep(i, Vec.size())chmin(ma, Vec[i]);
return ma;
}
template <typename T, typename U>
inline T mymax(const T& a, const U& b) {
return a > b ? a : b;
}
template <typename T, typename U>
inline T mymin(const T& a, const U& b) {
return a < b ? a : b;
}
#define cy cout << "Yes" << endl, exit(0)
#define cn cout << "No" << endl, exit(0)
//reduce(all(a)) 全ての和
#define イキスギィ！ ;
#define イクイク！ ;
#define ンアッー！ ;
#define 最後まで見てくれてありがとナス！ ;
#define ライブラリを借りるときはTwitterで言ってくれると喜びます 0
#define by元祖のヨッシー 0;
#define Twitterのidは quick_exit(0)
#define yosshi9990 ;
#define 枕がデカすぎます！ exit(0);
array<int, 8>dx = { 1,0,-1,0,1,-1,-1,1 };
array<int, 8>dy = { 0,1,0,-1,1,1,-1,-1 };
using mint = atcoder::modint998244353;
vector<int>modsok{ 1 };
inline ll kaijomod(const int& n, const int& mod = 998244353) {
if (n < modsok.size())return modsok[n];
for (int i = modsok.size(); i < n+1; ++i) {
modsok.emplace_back((((long long)modsok.back()) * i) % mod);
}
return modsok[n];
}
inline ll nCrmod(const int & n, const int& r,const int& mod = 998244353) {
return (kaijomod(n, mod) * inv_mod((kaijomod(n - r, mod) * kaijomod(r, mod)) % mod, mod)) % mod;
}
#ifdef BOOST_VERSION
inline cpp_int kaijo(ll n) {
cpp_int a = 1;
repa(i, n)a *= i;
return a;
}
#endif
inline bool iskaibun(const string& s) {
for (int i = 0; i < s.size() / 2; ++i) {
if (s[i] != s[s.size() - i - 1])
return false;
}
return true;
}
vector<long long>insuubunkai(long long n) {
vector<long long>ans;
for (long long i = 2; i * i < n; ++i) {
while (n % i == 0) {
ans.emplace_back(i);
n /= i;
}
}
if (n != 1)ans.emplace_back(n);
return ans;
}
template<class T>
inline set<T> to_set(const vector<T>& v) {
set<T>se;
for (int i = 0; i < v.size(); ++i)se.emplace(v[i]);
return se;
}
template<class T>
inline multiset<T> to_multiset(const vector<T>& v) {
multiset<T>se;
for (int i = 0; i < v.size(); ++i)se.emplace(v[i]);
return se;
}
template<class T, class U>
inline bool contains(const vector<T>& v, const U& a) {
auto low = lower_bound(v.begin(), v.end(), a);
if (low != v.end() && *low == a)return true;
else return false;
}
inline pair<long long, long long> extgcd(const long long& a, const long long& b) {
if (b == 0) return make_pair(1, 0);
long long x, y;
tie(y, x) = extgcd(b, a % b);
y -= a / b * x;
return make_pair(x, y);
}
inline vector<vector<int>>decide_edge(const vector<vector<int>>& G, const int& root) {
int N = G.size();
vector<bool> seen(N);
stack<int> que;
que.emplace(root);
seen[root] = true;
vector<vector<int>>ans(N);
while (!que.empty()) {
int v = que.top();
que.pop();
for (const int& w : G[v]) {
if (!seen[w]) {
ans[v].emplace_back(w);
seen[w] = true;
que.emplace(w);
}
}
}
return ans;
}
//mint op(mint a, mint b) { return 0; }
//mint mapp(mint f, mint x) { return f + x; }
//mint com(mint f, mint x) { return f + x; }
//mint e() { return 0; }
//mint id() { return 0; }
namespace {
struct Setup {
Setup() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(20);
at_quick_exit([] {cout << flush; });
}
//~Setup() {
イキスギィ！
イクイク！
ンアッー！
//枕がデカすぎます！
//}
} _setup;
}
inline string reversed(string s) {
reverse(all(s));
return s;
}
template<class T>
inline T mod(T a, T b) {
if (a < 0)a += (1 - a / b) * b;
return a % b;
}
#define zaatu(V) sort(all(V)),(V).erase(unique((V).begin(), (V).end()), (V).end())
#define zaatufind(V,i)lower_bound((V).begin(),(V).end(),(i))-(V).begin()
#define Graphhamidasi(i,j,H,W,DxNumber)(0<=i+dx[DxNumber]&&i+dx[DxNumber]<H&&0<=j+dy[DxNumber]&&j+dy[DxNumber]<W?true:false)
#define tograph(i,j,W)((i)*(W)+(j))
//using dynamic_bitset = boost::dynamic_bitset<>;
inline istream& operator>>(istream& is, modint& v) {
long long nu;
is >> nu;
v = nu;
return is;
}
inline istream& operator>>(istream& is, modint1000000007& v) {
long long nu;
is >> nu;
v = nu;
return is;
}
inline istream& operator>>(istream& is, modint998244353& v) {
long long nu;
is >> nu;
v = nu;
return is;
}
inline ll meguru_search(ll ng,ll ok,const function<bool(ll)> &isOK) {
/* ok と ng のどちらが大きいかわからないことを考慮 */
while (abs(ok - ng) > 1) {
ll mid = min(ok, ng) + abs(ok - ng) / 2;
if (isOK(mid))
ok = mid;
else
ng = mid;
}
return ok;
}
template<class T>
vector<int> LIS(const vector<T>&v) {
vector<T>ans(v.size(), std::numeric_limits<T>::max());
vector<int>dp(v.size());
for (int i = 0; i < v.size(); ++i) {
int t = lower_bound(ans.begin(), ans.end(), v[i]) - ans.begin();
ans[t] = v[i];
dp[i] = t + 1;
}
return dp;
}
template<class T, class U>
void mapadd(unordered_map<T, U>& ma, T val) {
ma[val] += 1;
}
template<class T, class U>
void maperase(unordered_map<T, U>& ma, T val) {
ma[val] -= 1;
if (ma[val] == 0)ma.erase(val);
}
template<class T, class U>
void mapadd(map<T, U>& ma, T val) {
ma[val] += 1;
}
template<class T, class U>
void maperase(map<T, U>& ma, T val) {
ma[val] -= 1;
if (ma[val] == 0)ma.erase(val);
}
struct AngelBeats {
using i64 = long long;
static constexpr i64 INFa = numeric_limits<i64>::max() / 2.1;
struct alignas(32) Node {
i64 sum = 0, g1 = 0, l1 = 0;
i64 g2 = -INFa, gc = 1, l2 = INFa, lc = 1, add = 0;
};
vector<Node> v;
i64 n, log;
AngelBeats() {}
AngelBeats(int _n) : AngelBeats(vector<i64>(_n)) {}
AngelBeats(const vector<i64>& vc) {
n = 1, log = 0;
while (n < (int)vc.size()) n <<= 1, log++;
v.resize(2 * n);
for (i64 i = 0; i < (int)vc.size(); ++i) {
v[i + n].sum = v[i + n].g1 = v[i + n].l1 = vc[i];
}
for (i64 i = n - 1; i; --i) update(i);
}
void range_chmin(int l, int r, i64 x) { inner_apply<1>(l, r, x); }
void range_chmax(int l, int r, i64 x) { inner_apply<2>(l, r, x); }
void range_add(int l, int r, i64 x) { inner_apply<3>(l, r, x); }
void range_update(int l, int r, i64 x) { inner_apply<4>(l, r, x); }
i64 range_min(int l, int r) { return inner_fold<1>(l, r); }
i64 range_max(int l, int r) { return inner_fold<2>(l, r); }
i64 range_sum(int l, int r) { return inner_fold<3>(l, r); }
private:
void update(int k) {
Node& p = v[k];
Node& l = v[k * 2 + 0];
Node& r = v[k * 2 + 1];
p.sum = l.sum + r.sum;
if (l.g1 == r.g1) {
p.g1 = l.g1;
p.g2 = max(l.g2, r.g2);
p.gc = l.gc + r.gc;
}
else {
bool f = l.g1 > r.g1;
p.g1 = f ? l.g1 : r.g1;
p.gc = f ? l.gc : r.gc;
p.g2 = max(f ? r.g1 : l.g1, f ? l.g2 : r.g2);
}
if (l.l1 == r.l1) {
p.l1 = l.l1;
p.l2 = min(l.l2, r.l2);
p.lc = l.lc + r.lc;
}
else {
bool f = l.l1 < r.l1;
p.l1 = f ? l.l1 : r.l1;
p.lc = f ? l.lc : r.lc;
p.l2 = min(f ? r.l1 : l.l1, f ? l.l2 : r.l2);
}
}
void push_add(int k, i64 x) {
Node& p = v[k];
p.sum += x << (log + __builtin_clz(k) - 31);
p.g1 += x;
p.l1 += x;
if (p.g2 != -INFa) p.g2 += x;
if (p.l2 != INFa) p.l2 += x;
p.add += x;
}
void push_min(int k, i64 x) {
Node& p = v[k];
p.sum += (x - p.g1) * p.gc;
if (p.l1 == p.g1) p.l1 = x;
if (p.l2 == p.g1) p.l2 = x;
p.g1 = x;
}
void push_max(int k, i64 x) {
Node& p = v[k];
p.sum += (x - p.l1) * p.lc;
if (p.g1 == p.l1) p.g1 = x;
if (p.g2 == p.l1) p.g2 = x;
p.l1 = x;
}
void push(int k) {
Node& p = v[k];
if (p.add != 0) {
push_add(k * 2 + 0, p.add);
push_add(k * 2 + 1, p.add);
p.add = 0;
}
if (p.g1 < v[k * 2 + 0].g1) push_min(k * 2 + 0, p.g1);
if (p.l1 > v[k * 2 + 0].l1) push_max(k * 2 + 0, p.l1);
if (p.g1 < v[k * 2 + 1].g1) push_min(k * 2 + 1, p.g1);
if (p.l1 > v[k * 2 + 1].l1) push_max(k * 2 + 1, p.l1);
}
void subtree_chmin(int k, i64 x) {
if (v[k].g1 <= x) return;
if (v[k].g2 < x) {
push_min(k, x);
return;
}
push(k);
subtree_chmin(k * 2 + 0, x);
subtree_chmin(k * 2 + 1, x);
update(k);
}
void subtree_chmax(int k, i64 x) {
if (x <= v[k].l1) return;
if (x < v[k].l2) {
push_max(k, x);
return;
}
push(k);
subtree_chmax(k * 2 + 0, x);
subtree_chmax(k * 2 + 1, x);
update(k);
}
template <int cmd>
inline void _apply(int k, i64 x) {
if constexpr (cmd == 1) subtree_chmin(k, x);
if constexpr (cmd == 2) subtree_chmax(k, x);
if constexpr (cmd == 3) push_add(k, x);
if constexpr (cmd == 4) subtree_chmin(k, x), subtree_chmax(k, x);
}
template <int cmd>
void inner_apply(int l, int r, i64 x) {
if (l == r) return;
l += n, r += n;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) _apply<cmd>(l++, x);
if (r & 1) _apply<cmd>(--r, x);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <int cmd>
inline i64 e() {
if constexpr (cmd == 1) return INFa;
if constexpr (cmd == 2) return -INFa;
return 0;
}
template <int cmd>
inline void op(i64& a, const Node& b) {
if constexpr (cmd == 1) a = min(a, b.l1);
if constexpr (cmd == 2) a = max(a, b.g1);
if constexpr (cmd == 3) a += b.sum;
}
template <int cmd>
i64 inner_fold(int l, int r) {
if (l == r) return e<cmd>();
l += n, r += n;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
i64 lx = e<cmd>(), rx = e<cmd>();
while (l < r) {
if (l & 1) op<cmd>(lx, v[l++]);
if (r & 1) op<cmd>(rx, v[--r]);
l >>= 1;
r >>= 1;
}
if constexpr (cmd == 1) lx = min(lx, rx);
if constexpr (cmd == 2) lx = max(lx, rx);
if constexpr (cmd == 3) lx += rx;
return lx;
}
};
/**
* @brief Range Chmin Chmax Add Update Range Min Max Sum Segment Tree Beats!
* @docs docs/segment-tree/segment-tree-beats.md
*/
struct Mo {
private:
int64_t hilbertorder(int x, int y) {
int64_t d = 0;
for (int s = 1 << logn - 1; s; s >>= 1) {
bool rx = x & s, ry = y & s;
d = d << 2 | rx * 3 ^ static_cast<int>(ry);
if (ry) continue;
if (rx) {
x = maxn - x;
y = maxn - y;
}
swap(x, y);
}
return d;
}
public:
int maxn, logn;
int width;
vector<int> left, right, order;
Mo(int N, int Q) : order(Q) {
width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));
iota(begin(order), end(order), 0);
logn = (32 - __builtin_clz((unsigned)N));
maxn = 1 << logn;
}
void insert(int l, int r) { /* [l, r) */
left.emplace_back(l);
right.emplace_back(r);
}
template <typename AL, typename AR, typename DL, typename DR, typename REM>
void run(const AL& add_left, const AR& add_right, const DL& delete_left,
const DR& delete_right, const REM& rem) {
assert(left.size() == order.size());
vector<int64_t>hilbertordered(left.size());
for (int i = 0; i < left.size(); ++i) hilbertordered[i] = hilbertorder(left[i], right[i]);
sort(begin(order), end(order), [&](int a, int b) {
//return left[a] / width < left[b] / width || (left[a] / width == left[b] / width && (((left[a] / width) & 1) == 0 ? right[a] < right[b] : right[b] < right[a]));
return hilbertordered[a] < hilbertordered[b];
});
int nl = 0, nr = 0;
for (auto idx : order) {
while (nl > left[idx]) add_left(--nl);
while (nr < right[idx]) add_right(nr++);
while (nl < left[idx]) delete_left(nl++);
while (nr > right[idx]) delete_right(--nr);
rem(idx);
}
}
};
template <class S, auto Op, auto E>
struct SegmentTree {
S op(S a, S b)const { return Op(a, b); }
S e() const { return E(); }
private:
int _n, size, log;
std::vector<S> d;
pair<int, int> ceil_pow2(int n) {
int x = 0; int t = 1;
while ((t) < (unsigned int)(n)) t *= 4, ++x;
return make_pair(x, t);
}
void update(int k) { d[k] = op(op(op(d[4 * k], d[4 * k + 1]), d[4 * k + 2]), d[4 * k + 3]); }
public:
SegmentTree() : SegmentTree(0) {}
explicit SegmentTree(int n) : SegmentTree(std::vector<S>(n, e())) {}
explicit SegmentTree(const std::vector<S>& v) : _n(int(v.size())) {
auto to = ceil_pow2(_n);
log = to.first, size = to.second;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size / 2-1; i >= 1; i--) {
update(i);
}
}
void set(int p, const S& x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 0; i < log; i++) {
update(p >>= 2);
}
}
//void stopset(int p, const S& x) {
// assert(0 <= p && p < _n);
// p += size;
// d[p] = x;
// for (int i = 0; i < log; i++) {
// update(p >> 2);
// if (d[p >> 2] != d[p]) {
// break;
// }
// p >>= 2;
// }
//}
S get(const int& p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if ((l & 3) == 1) {
sml = op(sml, d[l++]);
if (l < r) {
sml = op(sml, d[l++]);
}
if (l < r) {
sml = op(sml, d[l++]);
}
}
else if ((l & 3) == 2) {
sml = op(sml, d[l++]);
if (l < r) {
sml = op(sml, d[l++]);
}
}
else if ((l & 3) == 3) {
sml = op(sml, d[l++]);
}
if (l < r) {
if ((r & 3) == 3) {
smr = op(d[--r], smr);
if (l < r) {
smr = op(d[--r], smr);
}
if (l < r) {
smr = op(d[--r], smr);
}
}
else if ((r & 3) == 2) {
smr = op(d[--r], smr);
if (l < r) {
smr = op(d[--r], smr);
}
}
else if ((r & 3) == 1) {
smr = op(d[--r], smr);
}
}
l >>= 2;
r >>= 2;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while ((l & 3) == 0) l >>= 2;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (4 * l);
while (f(op(sm, d[l])) && (l & 3) != 3) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while (((l & -l) != l) || (__builtin_ctz((unsigned)l) & 1));
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r & 3)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (4 * r + 3);
while (f(op(d[r], sm)) && (r & 3) != 0) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r || (__builtin_ctz((unsigned)r) & 1));
return 0;
}
};
template<class T>
inline void merge(T& a, T& b) {
if (a.size() < b.size()) {
swap(a, b);
}
while (!b.empty()) {
a.emplace(b.top());
b.pop();
}
}
long long kiriage(long long a, long long b) {
return (a + b - 1) / b;
}
#ifdef BOOST_VERSION
const int128_t hashmod = 11451419198104545;
int128_t to_hash(const vector<int>& s) {
int128_t ans = 0;
for (int i = 0; i < s.size(); ++i) {
ans += s[i] + 1;
if (ans > hashmod)
ans %= hashmod;
ans *= 200002;
if (ans > hashmod)
ans %= hashmod;
}
return ans;
}
void add_hash(int128_t& ans,const char& s) {
ans += (s - 'a') + 1;
ans *= 27;
ans %= hashmod;
}
#include <boost/sort/spreadsort/integer_sort.hpp>
#include <boost/sort/pdqsort/pdqsort.hpp>
using boost::sort::pdqsort;
using boost::sort::spreadsort::integer_sort;
#endif
template<class T>
bool inlr(T l, T r, T v) {
return l <= v && v < r;
}
// function<void(int)>func = [&](int v) { };
#define fin quick_exit(0);
int op(int a, int b) {
return a > b ? a : b;
}
int e() { return -1; }
int v;
bool f(int seg_val) { return seg_val < v; }
int main() {
int n, q;
cin >> n >> q;
vector<int> a(n);
cin >> a;
segtree<int, op, e> st(a);
while (q--) {
int t;
cin >> t;
if (t == 1) {
int x, v;
cin >> x >> v;
x--;
if (st.get(x) < v) {
st.set(x, v);
}
else
st.set(x, v);
}
if (t == 2) {
int l, r;
cin >> l >> r;
l--;
cout << (st.prod(l, r)) << endl;
}
if (t == 3) {
int x;
cin >> x >> v;
x--;
cout << (st.max_right<f>(x) + 1) << endl;
}
}
exit(0) yosshi9990
'o' ^0^ -~- -0- ~-~ +0+ 0-0 *0* 0*0;
}
Submission Info
| Submission Time |
|
| Task |
J - Segment Tree |
| User |
yoss |
| Language |
C++ 23 (gcc 12.2) |
| Score |
100 |
| Code Size |
64130 Byte |
| Status |
AC |
| Exec Time |
58 ms |
| Memory |
6408 KiB |
Compile Error
Main.cpp:193:12: warning: extra tokens at end of #ifdef directive
193 | #ifdef YAJU&U
| ^
Main.cpp: In function ‘std::vector<long long int> Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)’:
Main.cpp:502:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
502 | for (int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
Main.cpp:510:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
510 | for (int i = 0; i < G[v].size(); ++i) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function ‘std::vector<std::vector<long long int> > Dijkstra_all(const std::vector<std::vector<Edge> >&)’:
Main.cpp:540:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
540 | for (int j = 0; j < G[v].size(); ++j) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function ‘std::vector<int> BFS_on_tree(const std::vector<std::vector<Edge> >&, const int&)’:
Main.cpp:613:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
613 | for (int i = 0; i < G[v].size(); ++i) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function ‘ll kaijomod(const int&, const int&)’:
Main.cpp:847:11: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
847 | if (n < modsok.size())return modsok[n];
| ~~^~~~~~~~~~~~~~~
Main.cpp: In function ‘bool iskaibun(const std::string&)’:
Main.cpp:864:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
864 | for (int i = 0; i < s.size() / 2; ++i) {
| ~~^~~~~~~~~~~~~~
Main.cpp: In member function ‘int64_t Mo::hilbertorder(int, int)’:
Main.cpp:1227:32: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
1227 | for (int s = 1 << logn - 1; s; s >>= 1) {
| ~~~~~^~~
Main.cpp:1229:33: warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]
1229 | d = d << 2 | rx * 3 ^ static_cast<int>(ry);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function ‘boost::multiprecision::int128_t to_hash(const std::vector<int>&)’:
Main.cpp:1447:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
1447 | for (int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:1514:30: warning: suggest parentheses around arithmetic in operand of ‘^’ [-Wparentheses]
1514 | 'o' ^0^ -~- -0- ~-~ +0+ 0-0 *0* 0*0;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~
Main.cpp:1514:11: warning: statement has no effect [-Wunused-value]
1514 | 'o' ^0^ -~- -0- ~-~ +0+ 0-0 *0* 0*0;
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:21,
from Main.cpp:132:
/opt/boost/gcc/include/boost/heap/detail/stable_heap.hpp: In instantiation of ‘boost::heap::detail::size_holder<false, SizeType>::size_holder(const boost::heap::detail::size_holder<false, SizeType>&) [with SizeType = long unsigned int]’:
/opt/boost/gcc/include/boost/heap/detail/stable_heap.hpp:188:68: required from ‘boost::heap::detail::heap_base<T, Cmp, constant_time_size, StabilityCounterType, stable>::heap_base(const boost::heap::detail::heap_base<T, Cmp, constant_time_size, StabilityCounterType, stable>&) [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; Cmp = std::less<Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair>; bool constant_time_size = false; StabilityCounterType = long unsigned int; bool stable = false]’
/opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:339:64: required from ‘boost::heap::detail::d_ary_heap<T, BoundArgs, IndexUpdater>::size_type boost::heap::detail::d_ary_heap<T, BoundArgs, IndexUpdater>::top_child_index(size_type) const [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; BoundArgs = boost::parameter::aux::flat_like_arg_list<boost::parameter::aux::flat_like_arg_tuple<boost::heap::tag::arity, boost::heap::arity<5>, std::integral_constant<bool, true> > >; IndexUpdater = boost::heap::detail::nop_index_updater; size_type = long unsigned int]’
/opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:289:41: required from ‘void boost::heap::detail::d_ary_heap<T, BoundArgs, IndexUpdater>::siftdown(size_type) [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; BoundArgs = boost::parameter::aux::flat_like_arg_list<boost::parameter::aux::flat_like_arg_tuple<boost::heap::tag::arity, boost::heap::arity<5>, std::integral_constant<bool, true> > >; IndexUpdater = boost::heap::detail::nop_index_updater; size_type = long unsigned int]’
/opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:240:9: required from ‘void boost::heap::detail::d_ary_heap<T, BoundArgs, IndexUpdater>::pop() [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; BoundArgs = boost::parameter::aux::flat_like_arg_list<boost::parameter::aux::flat_like_arg_tuple<boost::heap::tag::arity, boost::heap::arity<5>, std::integral_constant<bool, true> > >; IndexUpdater = boost::heap::detail::nop_index_updater]’
/opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:761:21: required from ‘void boost::heap::d_ary_heap<T, A0, A1, A2, A3, A4, A5>::pop() [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; A0 = boost::heap::arity<5>; A1 = boost::parameter::void_; A2 = boost::parameter::void_; A3 = boost::parameter::void_; A4 = boost::parameter::void_; A5 = boost::parameter::void_]’
Main.cpp:508:16: required from here
/opt/boost/gcc/include/boost/heap/detail/stable_heap.hpp:103:37: warning: unused parameter ‘rhs’ [-Wunused-parameter]
103 | size_holder(size_holder const & rhs) BOOST_NOEXCEPT
| ~~~~~~~~~~~~~~~~~~~~^~~
/opt/boost/gcc/include/boost/heap/detail/stable_heap.hpp: In instantiation of ‘boost::heap::detail::size_holder<false, SizeType>::size_holder(boost::heap::detail::size_holder<false, SizeType>&&) [with SizeType = long unsigned int]’:
/opt/boost/gcc/include/boost/heap/detail/stable_heap.hpp:178:72: required from ‘boost::heap::detail::heap_base<T, Cmp, constant_time_size, StabilityCounterType, stable>::heap_base(boost::heap::detail::heap_base<T, Cmp, constant_time_size, StabilityCounterType, stable>&&) [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; Cmp = std::less<Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair>; bool constant_time_size = false; StabilityCounterType = long unsigned int; bool stable = false]’
/usr/include/c++/12/bits/predefined_ops.h:165:14: required from ‘constexpr __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __gnu_cxx::__ops::__iter_comp_iter(_Compare) [with _Compare = boost::heap::detail::heap_base<Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair, std::less<Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair>, false, long unsigned int, false>]’
/usr/include/c++/12/bits/stl_algo.h:5718:39: required from ‘constexpr _FIter std::max_element(_FIter, _FIter, _Compare) [with _FIter = __gnu_cxx::__normal_iterator<const Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair*, vector<Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair, allocator<Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair> > >; _Compare = boost::heap::detail::heap_base<Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair, less<Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair>, false, long unsigned int, false>]’
/opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:339:64: required from ‘boost::heap::detail::d_ary_heap<T, BoundArgs, IndexUpdater>::size_type boost::heap::detail::d_ary_heap<T, BoundArgs, IndexUpdater>::top_child_index(size_type) const [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; BoundArgs = boost::parameter::aux::flat_like_arg_list<boost::parameter::aux::flat_like_arg_tuple<boost::heap::tag::arity, boost::heap::arity<5>, std::integral_constant<bool, true> > >; IndexUpdater = boost::heap::detail::nop_index_updater; size_type = long unsigned int]’
/opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:289:41: required from ‘void boost::heap::detail::d_ary_heap<T, BoundArgs, IndexUpdater>::siftdown(size_type) [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; BoundArgs = boost::parameter::aux::flat_like_arg_list<boost::parameter::aux::flat_like_arg_tuple<boost::heap::tag::arity, boost::heap::arity<5>, std::integral_constant<bool, true> > >; IndexUpdater = boost::heap::detail::nop_index_updater; size_type = long unsigned int]’
/opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:240:9: required from ‘void boost::heap::detail::d_ary_heap<T, BoundArgs, IndexUpdater>::pop() [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; BoundArgs = boost::parameter::aux::flat_like_arg_list<boost::parameter::aux::flat_like_arg_tuple<boost::heap::tag::arity, boost::heap::arity<5>, std::integral_constant<bool, true> > >; IndexUpdater = boost::heap::detail::nop_index_updater]’
/opt/boost/gcc/include/boost/heap/d_ary_heap.hpp:761:21: required from ‘void boost::heap::d_ary_heap<T, A0, A1, A2, A3, A4, A5>::pop() [with T = Dijkstra(const std::vector<std::vector<Edge> >&, const std::vector<int>&)::litepair; A0 = boost::heap::arity<5>; A1 = boost::parameter::void_; A2 = boost::parameter::void_; A3 = boost::parameter::void_; A4 = boost::parameter::void_; A5 = boost::parameter::void_]’
Main.cpp:508:16: required from here
/opt/boost/gcc/include/boost/heap/detail/stable_heap.hpp:100:32: warning: unused parameter ‘rhs’ [-Wunused-parameter]
100 | size_holder(size_holder && rhs) BOOST_NOEXCEPT
| ~~~~~~~~~~~~~~~^~~
Judge Result
| Set Name |
Sample |
All |
| Score / Max Score |
0 / 0 |
100 / 100 |
| Status |
|
|
| Set Name |
Test Cases |
| Sample |
00-sample-01.txt |
| All |
00-sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt |
| Case Name |
Status |
Exec Time |
Memory |
| 00-sample-01.txt |
AC |
1 ms |
3548 KiB |
| 01-01.txt |
AC |
1 ms |
3552 KiB |
| 01-02.txt |
AC |
47 ms |
6184 KiB |
| 01-03.txt |
AC |
46 ms |
5072 KiB |
| 01-04.txt |
AC |
7 ms |
3928 KiB |
| 01-05.txt |
AC |
14 ms |
3892 KiB |
| 01-06.txt |
AC |
36 ms |
6396 KiB |
| 01-07.txt |
AC |
13 ms |
3672 KiB |
| 01-08.txt |
AC |
33 ms |
6208 KiB |
| 01-09.txt |
AC |
29 ms |
6276 KiB |
| 01-10.txt |
AC |
23 ms |
4948 KiB |
| 01-11.txt |
AC |
11 ms |
4844 KiB |
| 01-12.txt |
AC |
58 ms |
6344 KiB |
| 01-13.txt |
AC |
53 ms |
6328 KiB |
| 01-14.txt |
AC |
58 ms |
6408 KiB |
| 01-15.txt |
AC |
53 ms |
6328 KiB |
| 01-16.txt |
AC |
58 ms |
6360 KiB |
| 01-17.txt |
AC |
54 ms |
6392 KiB |
| 01-18.txt |
AC |
58 ms |
6384 KiB |
| 01-19.txt |
AC |
53 ms |
6352 KiB |
| 01-20.txt |
AC |
58 ms |
6380 KiB |
| 01-21.txt |
AC |
53 ms |
6348 KiB |