; Memory mappings:
; 1..4N - segtree, 5e5.. - lazy
; 9e5 - value of N
; 9e5+1 - value of Q
; 9e5+2 - current ql
; 9e5+3 - current qr
; 9e5+4 - current x (if any), 9e5+5 - total answer, 9e5+6... - v l r and cnt for each recursion level
; register A - Q
; register B - curr node
; register C - curr l
; register D - curr r
; register E - stack pointer, registers F,G - temp, register H - cnt


IN A                                    ; cin >> n
MOV D 900000
STORE D A

IN A                                    ; cin >> Q

MOV RES A
JZ 677                                  ; if(Q==0) return 0
MOV C 1
SUB A C                                 ; Q--

IN B                                    ; cin >> t
IN C                                    ; cin >> l
IN D                                    ; cin >> r

MOV F 900002
STORE F C
MOV F 900003
STORE F D

MOV C 1
SUB B C
MOV RES B
JZ 252                                     ; if(t==1)
MOV E 900006 ; resetvame stack pointera
MOV H 0
MOV B 1
MOV C 1
MOV F 900000 ; indeks na N
LOAD F G
MOV D G ; stojnostta na N
MOV F 0
MOV G 900005
STORE G F







; query(v, l, r, ql, qr)
; purvo vikame push_lazyq(), vzima si parametrite ot B, C, D
MOV RES 0
JZ 497 ; push_lazyq

MOV F 900003
LOAD F F
CMP C F                                 ; if(l>qr) e 0
JZ 75                                 ; vrushtaneto kum roditelq
MOV F 900002
LOAD F F
MOV G 1
SUB F G
CMP D F                                 ; if(r<=ql-1) e 1
JNZ 75                                  ; vrushtaneto kum roditelq tuk

MOV RES 0
JZ 97 ; kum proverka za l>=ql && r<=qr

; vrushtame se kum roditelq
; vikame go sus stoinostite na roditelq - TEKUSHTIQ index e R
MOV G 1
SUB E G
LOAD E F
MOV H F          ; cnt
SUB E G
LOAD E F
MOV D F          ; r
SUB E G
LOAD E F
MOV C F          ; l
SUB E G
LOAD E F
MOV B F          ; node
; nashiq vruh shte mu e uvelichil cnt s 1
MOV F 1
ADD H F
; funkciqta ochakva da q viknem sus stack pointer nevkluchvasht neinite => ot tuk vikame
MOV RES 0
JZ 56 ; nachaloto na funkciqta

; proverka za l>=ql && r<=qr
; l>=ql
MOV F 900002
LOAD F F
CMP F C ; 0 ako ql>l, otivame v tqloto
JZ 149 ; tqlo

; r<=qr
MOV F 900003
LOAD F F
CMP D F ; 0 ako r>qr, otivame v tqloto
JZ 149 ; tqlo

; tuk l>=ql && r<=qr, izcqlo pokrit, trqbva da vurnem tekushtata stoinost
; neka zaredim jelanata stoinost v G
LOAD B G
; vrushtame se kum roditelq sus return value G
MOV F 900005
LOAD F F
ADD G F
MOV F 900005
STORE F G

; predi da se vurnem kum roditelq trqbva da proverim dali sme v korena, togava spirame i produljavame kum sledvashta zaqvka
; B==1
MOV RES B
MOV G 1
SUB RES G
JZ 486 ; print answer

; vikame go sus stoinostite na roditelq - TEKUSHTIQ index e R
MOV G 1
SUB E G
LOAD E F
MOV H F          ; cnt
SUB E G
LOAD E F
MOV D F          ; r
SUB E G
LOAD E F
MOV C F          ; l
SUB E G
LOAD E F
MOV B F          ; node
; nashiq vruh shte mu e uvelichil cnt s 1
MOV F 1
ADD H F
; funkciqta ochakva da q viknem sus stack pointer nevkluchvasht neinite => ot tuk vikame
MOV RES 0
JZ 56 ; nachaloto na funkciqta


; TQLO NA FUNKCIQTA
; smqtame si mid v G
MOV G C
ADD G D
MOV F 2
DIV G F ; mid e v G

; imame 3 sluchaq, ako cnt=0 vikame purvoto dete, ako cnt=1 vikame vtoroto, ako cnt=2 vrushtame kum parenta I UVELICHAVAME COUNTA MU
MOV F 2
SUB F H ; F=2-H
MOV RES F
JZ 213 ; KRAI NA FUNKCIQTA

MOV F 1
SUB F H ; F=1-H
MOV RES F
JZ 188 ; VTOROTO DETE SAMO

; purvo dete, slagame si neshtata v steka
STORE E B ; node
MOV F 1
ADD E F
STORE E C ; l
ADD E F
STORE E D ; r
ADD E F
STORE E H ; cnt
ADD E F ; nadqvam se che tova trqbva da e tuk
; vikame si deteto
; parametri
MOV F 2
MUL B F ; node*2
; l ostava
MOV D G ; mid
MOV H 0 ; no counter
; unconditional jump
MOV RES 0
JZ 56 ; nachalo na funkciqta

; vtoro dete, ne moje da se izpulnqt i dvete taka che e ok
STORE E B ; node
MOV F 1
ADD E F
STORE E C ; l
ADD E F
STORE E D ; r
ADD E F
STORE E H ; cnt
ADD E F ; nadqvam se che tova trqbva da e tuk
; vikame si deteto
; parametri
MOV F 2
MUL B F ; node*2
MOV F 1
ADD B F ; +1
MOV C G ; l=mid
ADD C F ; +1
; r ostava
MOV H 0 ; no counter
; unconditional jump
MOV RES 0
JZ 56 ; nachalo na funkciqta


; predi da se vurnem kum roditelq trqbva da proverim dali sme v korena, togava spirame i pechatame
; B==1
MOV RES B
MOV G 1
SUB RES G
JNZ 224 ; kum vrushtaneto

; veche moje da pechatame otgovora
MOV RES 0
JZ 486 ; print answer

; vrushtame se kum roditelq
; vikame go sus stoinostite na roditelq - TEKUSHTIQ index e R
MOV G 1
SUB E G
LOAD E F
MOV H F          ; cnt
SUB E G
LOAD E F
MOV D F          ; r
SUB E G
LOAD E F
MOV C F          ; l
SUB E G
LOAD E F
MOV B F          ; node
; nashiq vruh shte mu e uvelichil cnt s 1
MOV F 1
ADD H F
; funkciqta ochakva da q viknem sus stack pointer nevkluchvasht neinite => ot tuk vikame
MOV RES 0
JZ 56 ; nachaloto na funkciqta







; add query
IN F
MOV G 900004
STORE G F

; init na parametrite
MOV E 900006 ; resetvame stack pointera
MOV H 0
MOV B 1
MOV C 1
MOV F 900000 ; indeks na N
LOAD F G
MOV D G ; stojnostta na N
MOV F 0
MOV G 900005
STORE G F

; update(v, l, r, ql, qr, x)

; purvo vikame push_lazy
MOV RES 0
JZ 556 ; push_lazyupd1

MOV F 900003
LOAD F F
CMP C F                                 ; if(l>qr) e 0
JZ 289                                  ; vrushtaneto kum roditelq
MOV F 900002
LOAD F F
MOV G 1
SUB F G
CMP D F                                 ; if(r<=ql-1) e 1
JNZ 289                                  ; vrushtaneto kum roditelq tuk

MOV RES 0
JZ 311 ; kum proverka za l>=ql && r<=qr

; vrushtame se kum roditelq
; vikame go sus stoinostite na roditelq - TEKUSHTIQ index e R
MOV G 1
SUB E G
LOAD E F
MOV H F          ; cnt
SUB E G
LOAD E F
MOV D F          ; r
SUB E G
LOAD E F
MOV C F          ; l
SUB E G
LOAD E F
MOV B F          ; node
; nashiq vruh shte mu e uvelichil cnt s 1
MOV F 1
ADD H F
; funkciqta ochakva da q viknem sus stack pointer nevkluchvasht neinite => ot tuk vikame
MOV RES 0
JZ 269 ; nachaloto na funkciqta

; proverka za l>=ql && r<=qr
; l>=ql
MOV F 900002
LOAD F F
CMP F C ; 0 ako ql>l, otivame v tqloto
JZ 370 ; tqlo

; r<=qr
MOV F 900003
LOAD F F
CMP D F ; 0 ako r>qr, otivame v tqloto
JZ 370 ; tqlo

; tuk l>=ql && r<=qr, izcqlo pokrit, trqbva da uvelichim nasheto LAZY s x
; neka zaredim jelanata stoinost v G
MOV F 500000
ADD F B
LOAD F G
; uvelichavame s x
MOV F 900004
LOAD F F ; tova e x
ADD G F
MOV F 500000
ADD F B
STORE F G

; sled kato sme dobavili kum nasheto lazy vikame push lazy
MOV RES 0
JZ 617 ; push_lazyupd2

; predi da se vurnem kum roditelq trqbva da proverim dali sme v korena, togava spirame i produljavame kum sledvashta zaqvka
; B==1
MOV RES B
MOV G 1
SUB RES G
JZ 21 ; sledvashta zaqvka

; vikame go sus stoinostite na roditelq - TEKUSHTIQ index e R
MOV G 1
SUB E G
LOAD E F
MOV H F          ; cnt
SUB E G
LOAD E F
MOV D F          ; r
SUB E G
LOAD E F
MOV C F          ; l
SUB E G
LOAD E F
MOV B F          ; node
; nashiq vruh shte mu e uvelichil cnt s 1
MOV F 1
ADD H F
; funkciqta ochakva da q viknem sus stack pointer nevkluchvasht neinite => ot tuk vikame
MOV RES 0
JZ 269 ; nachaloto na funkciqta


; TQLO NA FUNKCIQTA
; smqtame si mid v G
MOV G C
ADD G D
MOV F 2
DIV G F ; mid e v G

; imame 3 sluchaq, ako cnt=0 vikame purvoto dete, ako cnt=1 vikame vtoroto, ako cnt=2 vrushtame kum parenta I UVELICHAVAME COUNTA MU
MOV F 2
SUB F H ; F=2-H
MOV RES F
JZ 434 ; KRAI NA FUNKCIQTA

MOV F 1
SUB F H ; F=1-H
MOV RES F
JZ 409 ; VTOROTO DETE SAMO

; purvo dete, slagame si neshtata v steka
STORE E B ; node
MOV F 1
ADD E F
STORE E C ; l
ADD E F
STORE E D ; r
ADD E F
STORE E H ; cnt
ADD E F ; nadqvam se che tova trqbva da e tuk
; vikame si deteto
; parametri
MOV F 2
MUL B F ; node*2
; l ostava
MOV D G ; mid
MOV H 0 ; no counter
; unconditional jump
MOV RES 0
JZ 269 ; nachalo na funkciqta

; vtoro dete, ne moje da se izpulnqt i dvete taka che e ok
STORE E B ; node
MOV F 1
ADD E F
STORE E C ; l
ADD E F
STORE E D ; r
ADD E F
STORE E H ; cnt
ADD E F ; nadqvam se che tova trqbva da e tuk
; vikame si deteto
; parametri
MOV F 2
MUL B F ; node*2
MOV F 1
ADD B F ; +1
MOV C G ; l=mid
ADD C F ; +1
; r ostava
MOV H 0 ; no counter
; unconditional jump
MOV RES 0
JZ 269 ; nachalo na funkciqta


; iskame nashiq vruh da ima sumata na decata mu, tova trqbva pak da checknem
; tree[v]=tree[v<<1]+tree[v<<1|1]
MOV F B
MOV G 2
MUL F G ; f = node*2
LOAD F F ; stoinost na deteto
STORE B F ; slagame na purvoto dete
MOV F B
MOV G 2
MUL F G ; f = node*2
MOV G 1
ADD F G ; f = node*2 + 1
LOAD F F ; stoinost na dqsnoto dete
LOAD B G ; tekushtata stoinost otiva v G
ADD G F ; dobavqme nashata
STORE B G ; slagame novata ni stoinost

; predi da se vurnem kum roditelq trqbva da proverim dali sme v korena, togava spirame i produljavame kum sledvashta zaqvka
; B==1
MOV RES B
MOV G 1
SUB RES G
JNZ 462 ; kum vrushtaneto

; sledvashta zaqvka
MOV RES 0
JZ 21 ; query loop

; vrushtame se kum roditelq
; vikame go sus stoinostite na roditelq - TEKUSHTIQ index e R
MOV G 1
SUB E G
LOAD E F
MOV H F          ; cnt
SUB E G
LOAD E F
MOV D F          ; r
SUB E G
LOAD E F
MOV C F          ; l
SUB E G
LOAD E F
MOV B F          ; node
; nashiq vruh shte mu e uvelichil cnt s 1
MOV F 1
ADD H F
; funkciqta ochakva da q viknem sus stack pointer nevkluchvasht neinite => ot tuk vikame
MOV RES 0
JZ 269 ; nachaloto na funkciqta



; print answer
MOV E 900005
LOAD E E
OUT E
; unconditional jump
MOV RES 0
JZ 21




; push_lazyq()

; ako !lazy[v] returnvame
; lazyind = v+5e5
MOV F 500000
ADD F B
LOAD F RES
JZ 61 ; sled vikaneto na funkciqta ni

MOV F D
SUB F C
MOV G 1
ADD F G ; f = r-l+1
MUL F RES ; f*=lazy
LOAD B G ; g = tree[v]
ADD G F ; g+=(r-l+1)*lazy
STORE B G ; tree[v]=g

; ako l!=r
MOV G RES
MOV RES C
SUB RES D
JZ 544 ; ako sa ravni, kum zanulqvane na lazy
MOV RES G

; lazy[v<<1]+=lazy[v]
MOV F B
MOV G 2
MUL F G ; v*2
MOV G 500000
ADD F G
LOAD F G ; g = lazy[v<<1]
ADD G RES ; g += lazy[v]
STORE F G ; lazy[v<<1]=g

; lazy[v<<1+1]+=lazy[v]
MOV F B
MOV G 2
MUL F G ; v*2
MOV G 500000
ADD F G
MOV G 1
ADD F G ; v*2 + 1
LOAD F G ; g = lazy[v<<1|1]
ADD G RES ; g += lazy[v]
STORE F G ; lazy[v<<1|1]=g

; zanulqvame nasheto lazy
MOV F 500000
ADD F B
MOV G 0
STORE F G ; lazy[v]=0

; vrushtame se kum viknaliq funkciqta
MOV RES 0
JZ 61 ; koito vika funkciqta



; push_lazyupd1(), v nachaloto na update (tri otdelni za da opravim jz, jnz)

; ako !lazy[v] returnvame
; lazyind = v+5e5
MOV F 500000
ADD F B
LOAD F RES
JZ 275 ; sled vikaneto na funkciqta ni

MOV F D
SUB F C
MOV G 1
ADD F G ; f = r-l+1
MUL F RES ; f*=lazy
LOAD B G ; g = tree[v]
ADD G F ; g+=(r-l+1)*lazy
STORE B G ; tree[v]=g

; ako l!=r
MOV G RES
MOV RES C
SUB RES D
JZ 603 ; ako sa ravni, kum zanulqvane na lazy
MOV RES G

; lazy[v<<1]+=lazy[v]
MOV F B
MOV G 2
MUL F G ; v*2
MOV G 500000
ADD F G
LOAD F G ; g = lazy[v<<1]
ADD G RES ; g += lazy[v]
STORE F G ; lazy[v<<1]=g

; lazy[v<<1+1]+=lazy[v]
MOV F B
MOV G 2
MUL F G ; v*2
MOV G 500000
ADD F G
MOV G 1
ADD F G ; v*2 + 1
LOAD F G ; g = lazy[v<<1|1]
ADD G RES ; g += lazy[v]
STORE F G ; lazy[v<<1|1]=g

; zanulqvame nasheto lazy
MOV F 500000
ADD F B
MOV G 0
STORE F G ; lazy[v]=0

; vrushtame se kum viknaliq funkciqta
MOV RES 0
JZ 275 ; koito vika funkciqta





; push_lazyupd2(), pri pulno pripokrivane v update

; ako !lazy[v] returnvame
; lazyind = v+5e5
MOV F 500000
ADD F B
LOAD F RES
JZ 341 ; sled vikaneto na funkciqta ni

MOV F D
SUB F C
MOV G 1
ADD F G ; f = r-l+1
MUL F RES ; f*=lazy
LOAD B G ; g = tree[v]
ADD G F ; g+=(r-l+1)*lazy
STORE B G ; tree[v]=g

; ako l!=r
MOV G RES
MOV RES C
SUB RES D
JZ 664 ; ako sa ravni, kum zanulqvane na lazy
MOV RES G

; lazy[v<<1]+=lazy[v]
MOV F B
MOV G 2
MUL F G ; v*2
MOV G 500000
ADD F G
LOAD F G ; g = lazy[v<<1]
ADD G RES ; g += lazy[v]
STORE F G ; lazy[v<<1]=g

; lazy[v<<1+1]+=lazy[v]
MOV F B
MOV G 2
MUL F G ; v*2
MOV G 500000
ADD F G
MOV G 1
ADD F G ; v*2 + 1
LOAD F G ; g = lazy[v<<1|1]
ADD G RES ; g += lazy[v]
STORE F G ; lazy[v<<1|1]=g

; zanulqvame nasheto lazy
MOV F 500000
ADD F B
MOV G 0
STORE F G ; lazy[v]=0

; vrushtame se kum viknaliq funkciqta
MOV RES 0
JZ 341 ; koito vika funkciqta




RETURN                                  ; return 0





; tova mi otne okolo 5 chasa