; Memory mappings:
; 1..4N - segtree
; 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 483                                      ; 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 248                                     ; 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)
MOV F 900003
LOAD F F
CMP C F                                 ; if(l>qr) e 0
JZ 71                                 ; 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 71                                  ; vrushtaneto kum roditelq tuk

MOV RES 0
JZ 93 ; 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 145 ; tqlo

; r<=qr
MOV F 900003
LOAD F F
CMP D F ; 0 ako r>qr, otivame v tqloto
JZ 145 ; 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 470 ; 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 209 ; KRAI NA FUNKCIQTA

MOV F 1
SUB F H ; F=1-H
MOV RES F
JZ 184 ; 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 220 ; kum vrushtaneto

; veche moje da pechatame otgovora
MOV RES 0
JZ 470 ; 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)
MOV F 900003
LOAD F F
CMP C F                                 ; if(l>qr) e 0
JZ 280                                  ; 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 280                                  ; vrushtaneto kum roditelq tuk

MOV RES 0
JZ 302 ; 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 265 ; 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 354 ; tqlo

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

; tuk l>=ql && r<=qr, izcqlo pokrit, trqbva da uvelichim tekushtata stoinost s x
; neka zaredim jelanata stoinost v G
LOAD B G
; uvelichavame s x
MOV F 900004
LOAD F F ; tova e x
ADD G F
MOV F 900004
STORE B 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 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 265 ; 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 418 ; KRAI NA FUNKCIQTA

MOV F 1
SUB F H ; F=1-H
MOV RES F
JZ 393 ; 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 265 ; 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 265 ; 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 446 ; 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 265 ; nachaloto na funkciqta



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






RETURN                                  ; return 0





; tova mi otne nad 3 chasa i polovina