/*
; ; i t t t t t i i i i i i t t t t t t t t t t t L G G L j j t t j j f f L D D t t t G G j f L L L D t j E G L E f t j D D D D G L L L L D D f i t j j j j j j 
, , ; ; i i i i i i i i i i i i t t t t t t t t t t f G G G L f f f f L L L G E f t t G G j L L L L D j t E D E j t t E D D L L L L L G D D t i t j j j j j j j 
, , , , ; i i ; ; ; ; i i i i i t t t t t t t t t t t j G G G G G D D E E K K E E t t L D f L L L L E j t E K f t t D E D L L L L G D D D t i i f j j j j E f j 
; , , , , , , , , , , , , ; ; i i t t t t G G G f t t t t j L G D D G f j j t t j t t f D f L L L L E t t E G t t f E D L L G D E E D j t i i j j j E f f j t t 
; ; ; ; , , , , , , , , ; , ; i i t t t t j G f f G j t t t t t t j f f L L G G j t t t E G L L L D D t t E t t t E E D E E K E L j t t i i f j f f f j j t t t 
i i ; ; ; ; ; ; ; ; ; ; ; ; ; i i t t t t t L L f j t t t t j f L G G G L L G G D L t t L E L L L E L t t L t t j E E K E G j t t t t i i L f f f j j t t t t t 
i i i i i i i i i i i i i ; , i i t t t t t t f j t t t t t f f f j L G L j j f L E D t t G E L G K j t j t t t E K E L t t t t t t i i L L f j j j t t t t t t 
t t t t t t t t t t t t i i ; ; i t t t t t t G f t t t t t j f f t t j E D f f f D E E t t D E E K j t t t t f K E j t t t t t t i i L L t j j j t t t t j j j 
t t t t t t t t t t t t t t ; ; i i t t t t t L L j t t t t t j f f t t L E E f f L G E E f t L E K t t t t t E G t t t t t t t i i L f E j j j t t t t t j j j 
j t t t t t t t t t t t t t i ; i i t t t t t j G f t t t t t i t i t t t f K E L L L L E K D j t L j t t t j G t j f t t t t i t L f j j G j j t t t j j j j j 
j j j j j j j j j j j t t t t ; ; i t t t t t j G f t t t t t i i i t t t t j E E G L L L G E E E G j t t t f t f L L f t t i j f j j j j f t t j j j j j j j j 
j j j j j j j j j j j j t t t ; ; i t t L f t t D j t t t t t i i i i t t t t t L E E E E E E E D L j t t t t t G L L L t i L f j j j j j j G t j j j j j j f f 
j j j j j j j j j j j t t t t i ; i t j L f j j D j t t t t t t i i i i j t t t t t L D E D G j t t t t t t t j G L L f t f t j j j j j j t G t j j j j f f f f 
j j j j j j j j j j j t t t t i ; ; i t L f f j G j t t t t t j i i i i i t t t t t t t t t t t t t t t t L D j L D L f f L t f j j j j t t K j D j j f f f f f 
j j j j j j j j j j j t t t i i ; ; i t t f j j D f t t t t t t t i i i i t t t t t t t t t t t t t j G E G t t t E L f f j L t j j j t t t j f f j f f f f f L 
t t t t t t j j j j t t t t i ; ; ; ; t i i i j D L t t t t t t t i i i i t G G L L f f j j f f G D E D f t t t j E f f j j K i j j t t t j j G f f f f f K E E 
t t t t t t t t t t t t t i ; , : , ; t i i i i f D f t t t t t t t i i i i j j G D D D D D E E E D L t t t t j G E f f j j j L j t t t j j j G f L E E E E E E 
t t t t t t t t t t t t i ; ; , : : , i i i i i i G L t t t t t t j i i i i t t t t j L G D D D G j t t t t j L L f f j j j j G j t t t j j f G L E E E E E E E 
t t t t t t t t t t t i i ; , : . . , , i i i i i i t f t t t t t t i i i i i j t t t t t t t t t t t t t j L f E f f j j j j K j t t j j E D G K D E E E E E E 
t t t t t t t t t t i i ; , : : . .   , ; i i i i i i i t j j t t t t i i i i t t t t t t t t t t t t t f f f f E f f f f j j j L j j K G G G f D D E K D G G G 
t t t t t t t t t i i ; , : : . .       ; ; , i i i i i i t t t t t t i i i i i j t t t t t t t t t t L L f f j f j j f E f f f L L L D G G G G G G G G G G G G 
i i i i i i i i j j j j t i i i i ; i i i i i ; ; i i i i i t t t t t i i i i i t t t t t t t t t t L L f t t E t t t t j j K K f f f f f L L L G G G G G G G G 
i i i i i i i i i i t i i i i i i t t i i i i i ; , ; i i i i t t t t i i i i i t t t t t t t t t L f f t t t t t t t t t t t f D L f f f L L L L L G G G G G G 
i i i i i ; ; ; ; ; ; ; i i i i i i i i i i i t t i ; , i i i t t t i i i i i i t t t t t t t t L f f t t t L t t L t t t t t t j L f f f f L L L L L G G G G G 
; ; ; ; ; ; ; ; ; , , , , , ; i i i t i ; i i i i t i ; ; i i t t t ; i i i i i t t t t t t j L f j i i i f t t t t t L t t t t t j f G f f L L L L L G G G G G 
; ; ; ; , , , , , , : : . : , ; i i t i , , , ; i t t i , i i t t j , i i i t i j t t t t L f f t i i E i t t t t t t t t L t t t t j f f L L L L L L G G G G G 
; , , , , : : : : : : : .   . , i i t t .   : ; i t t t , i i t t t , i i t t t j t t f L f f f i i E i i i i i t i i t t t D t t t j f f f K L L L G G G G G G 
, , : : : : : : : : : . .   . , i i t t ,   : ; i t t i , i t t t t , i i t t t G L L f f f i i E D i i i i f G G i i i t t j K t t G L f f f E D D G G G G G G 
: : : . . . . . . . . . . . . : i i t t ;   : ; i t t t , ; t t t t , i t t t t L L E E E E E i f i i i i i i G G G G t j j j j K j j j j f L D D D j K G G G G 
: . . . . .   . . . . . . . . : ; i t t i   : ; t t t t , ; t t t i , i t t t t L L f f i K K i f f i i i i i i i D D j f t i L j D j t f f K D D j j j j D G G 
. .                 . . . . . : ; i t t t . : ; t t t i , ; t t t i , i t t t t L L j i i E K i j L i i t i i i i j L D D L t j G L j i i L E D j j j j j j j G 
.                     . . : : : ; i t t t : : ; i t t t , , i t t i , i t t t j L f i i i W W i t f f i i i i i t f f t t L L G D j L t i i f j j j j j j j j j 
                      . . : : , ; i i t t ; , ; i t t t , ; i t t i , t t t t j f i i i D E E i t f f t i t i t f f t t t L j t D t f G t j f t t j j j j j j j 
                        . : , ; i i t t t i , i t t t t , ; i t t i i t t t t f i i i i L E E j t f G L i i i j G j t t t t j t L j G D L L t t t t t t t j j j 
                        : , ; i i t t t t i ; i t t t i , i i t i i t t t t t j i i i i G G D K t f L f j i i f f t t t f D G L G t j D G t t t t t t t t t j t 
                    . : , ; i i i t t t t t i t t t t i i i t t t i t t t t t t i i t i E L K G E K f f j f K L j t t j f j t j t t K L L E D t t t t t t t t L 
                  . : , i i i i t t t t t t t t t t t i i t t t t t t t t t t i i i t i D t D D f f f f j t t L f i t L j L t j j j f j j i G t t j t t t t L L 
            .   : , ; i i i i t t t t t t t t t t t t i t t t t t t t t t t t i i t i i i D i t j f f L f j t j G f i G j f t t f G f t D D L t t t t t i L L L 
        . , j , ; i i i i i t t t t t t t t t t t t t t t t t t t t t t t t j i t t t t t t t t j f f f f j t i L t D G t t t t t G f t L j t t t t t i L L L L 
        : i f ; i i i i i i t t t t t t t t t t t t t t t t t t t t t t t t t i t t t t t t t t f f f f K f j f t L G L D i j j G G j L f L t t t t i D L L L L 
      . i G L i i i i i i t t t t t t t t t t t t t t t t t t t t t t t t t t i t t t t t t t j f f f f f f j t G i L t t L j j L j j j j L L t t t j L L L L L 
  . : : j D f i i i i i i t t t t t t t t t t t t t t t t t t t t t t t j t t i t t t t t t t j f L f j f L f j t f G f L E L f j j t j G t j f E t L L L L L L 
: t , i L D t i i i i i t t t t t t t t t t t t t t t t t t t t t t j t t t t i t t t t t t t j f K j j f f f f t t t f L t j t D f t i f t j j j j G L L L L L 
, G i f G E i i i i i i t t t t t t t t t t t t t t t t t t t t j j t t t t t i t t t t i i t j f f j j j f E f j t t t t t t t t t j f t t j j j j j L L L L L 
j D t L D E i i i i i t t t t t t t t t t t t i i t t t t t j t t t t t j t t t t t t j t t j j f f t j j j f f f j t t t t t j t t t j t t j j j j j j j L L L 
L D f G D E i i i i t t t t t t t t t t t i i i i i i t j t t t t t t t t t t t j t j j j j j j G G t j j j j f f f j j j j t j t t t t . j j j j j j j j j L L 
G D G G E D i i i i t t t t t t t t t t i i i i i i t t i t t D j t t t t t t j j t j j j j j f G L t j j j j j f j j j j j j t f t t j f j j j j j f j j j j j 
G D D G E G i i i i t t t t t t t t t i i i i i t j i i i t j j j t t t t t j j j j j j j j j f f f t j f t j j j f j j j j j j f j j j j f j j j j j j j j j j 
G D D D E G i i i t t t t t i i i i i i i i t i j t i i t j j i j t t t t t j j j j j j j j j L f f L j j f t j i f j j j j j j j L j j j j f j j j j f j j j j 
G D D D K L t t i t t i t i i i i i i i i i ; i j t W K E K # # j t t t j j j j t j j j j j j f f t f t j L j j j j D j j f j j j f f j j j f f j j j j f j j j 
L G D D E f t t t t i i i i i i i i i i ; ; i j j i i L j i i i j t f t j j j j j j j j f j f f i i # K f f G W # j j L j j j j j j f f j j j G f j j j L f j j 
f G D D E f t t t t i i i i i i i t i ; ; ; i t t i i t i i i i t L t j f j j j j j j j f j E f i i i f G j f j j j t j L t j j j j j L j j j j f f j j j f f j 
j L D D E f t t t t t i i i i t , i ; ; ; ; i t i i t ; ; i i i i L t j f j j j j t j j f j f i i i i i f j j f j j j ; j f t j j j j j L j j j j f f j j j f f 
t L D D E f j t t t t t i t i i : ; ; ; ; ; f t i j ; ; ; ; i i i j t j f j j j j t j j f f f i i i i i i f j K L j j j t f D j t j j j j L j j j j f f j j D f 
t f G D D L j t t t t t t j : t i ; ; ; ; i j t i ; ; ; ; ; i i i i t j f j j j j j i t f f i i i i i i i i j j W L j j j j j j j t j j j t L f j j j f f j j f 
t j L D G L j t t t t t t t : j i i ; ; ; i j t t ; ; G ; ; i i i i E t K j j j j j j t f f i i i i i i i i i j j K f j j j j j j f t t j t t G f j j j L f f j 
t j f G G G j t t t t t t , i j i i ; ; i i t t ; ; i E W i f i i i i t f f L j j j t j D f i i i i i i i i i i t j f f j j j E i j L G t t t t t L j j j f f f 
t j L f G G j t t t t t t : i t i i i i i j t j D D E E K W K t i i i j f f L j j j j j G f i i i i i G t t t t t i j E f L j j G j ; L f f G t t t t j L L j f 
t t f f D D f t t t t t ; : i t i i i i i L t f D D E G G D K K f i i i E f f j j j L t t i i i t t j j # # # # # # # # # W L f G f j G L j f f j j j j j j j j 
t t f G G D G j t t t t , : i j i i i i i t D D D i i G E E K K K f i i j f f f j j f j t j ; i t j W W # # # # # # # # # W W i j j E j K L f f f f j j j j j j 
t t j E L D D f t t t t i : i t ; i i i ; t t D D i ; E E E t   , K i i i D f L j j f L t f i ; G W W W # E W W W W W W # # # W K j j D t D L f f f f f f j j j 
t t j E L D D G t t t i i : t j , i ; i ; t E ; D ; ; E E E E K K K i i i E f G j j j f j D i t W W j j W W W W i   ; W W # # W W t t t t t G L L f f j j j j j 
t t j D E L D D f t t i i : j j : i ; i i t t ; G ; ; K E E E D W K W i i i f f L j j f f t i K G t t i W W W W W # W W W L # W W K t t t t D j D G L f f j j j 
t t t L E G G D G t j i i : , j : i ; t i t t ; ; t ; ; j D D D W K W i i i D f j L j j j f j L i i i i K G G W E E W W W W j W L t t t t t t t t L D D f f f j 
t t t f K E L D D L t i i , : j : i , t i t t f ; D ; ; ; f f L f L W i i i i f i G G j f i G i i i i i G W E E E E D W W E W W t t t t j t t t t t t L L f f f 
t t t j K K D G D D j i i i : j , ; , t i , t t ; ; i ; D f G f f L E i i i i i D D i L j i i i i i i i G t G G G W G G i i W i t t t j t t j t t t t L G j t f 
t t t j E K D G D D G t i i : j t ; : j i D t t ; ; ; ; ; f j t f L i i i i i i i i i i i L i i i i i i K f G G L G G G G D i L t t t f t j t t t t t L K j t E 
t t t j D K E L G D D L , . : j i : , L i i t t ; ; ; ; ; j i ; t j i i i i i i i i i i i i i i i i i i i G L j j j L G t i i t t t D t f t t t t t t L E j t E 
t t t j f E E j L G D f   . : j : : ; L i i t t , ; ; ; ; ; i i i i i ; i i i i i i i i i i i i i t t t t G # D f E W t t t t t t G j f t t t t t t t L L j t G 
t t t t j E E L L G G :   . : : t . , i t i t t : ; ; ; i i i i i ;   i i i i i i i i i i i i t t t t t t t t t t t t t t t f t t f j t t t t t t t t L j j i f 
t t t t j D D D G G .     . : : ;   : : t i i t i ; ; ; i i i i i   i i i i i i i i i i i i i t t t t t t t t t t t t t t t t t L f f t t t t t t t t L j j i f 
t t t j L L D E E D .       . : ; , . : t i i t i ; ; ; i i i i     i i i i i i i i i i i i i t t t t t t t t t t t t t t L j L f f t i t t t t t j t D j t G f 
t j L f j j j L E D .         : . . . : ; t i i i ; ; ; i i i i , i i i i i i i i i i i i i i t t t t t t j t t j t t t t t f G f t t t t t t t t t t j D t f f 
j L f f j t t t L D .     . : : : .   . : t j i ; , ; ; ; i i i i i i i i i i i i i i i i i i t t t t t t t j j t t t t j f t f f t t t t t t t j t t D L E G f 
L L L j j t i t j i   . . . . .       . : : t j ; , ; ; ; i i i i i i i i i i i i i i i i i i t t t t t t t t t t t t t f j i f t t , t t j t t j t G G L L t f 
L L L f j t i t j t   . : . .           : ; , t t : ; ; ; ; ; i i i i i i i i i i i i i i i i i t t t t t t t t t t t j f i L f t t t t t t t t t t j D L D t f 
L L L f j j t j j j , . : . .           : i i : t : , ; ; ; ; ; ; i i i i i i i i i i i i i i i i t t t t t t t t t L j j i f t t t t t f t t f t t D j f t G f 
L L L L f f G D f i . : . . .           : ; ; i i , , ; ; ; ; ; i i i i i i i i i i i i i i i i i i t t t t t t t t t f i i f i t t t t j t t f t t L G t f f f 
f f L L L f L D f : . : . .             : ; ; i i ; : ; ; ; ; ; ; i i i i i i i i i i i i i i i i i i i t t t t t j t j i E f t t , t f t t E j t t f j j f f f 
t j t j f f f i : : : : . .             : ; ; i i i : , ; ; ; ; ; i i i i i i i i i i i i i i i i i i i i i i i i i j j i j t i t j t f t t f t t t f i L f f f 
t j j i ; ; ; : . : : . .               : ; ; t i i , , ; ; ; ; ; i i i i i i i i i i i i i i i i i i i i i i i t i j i K G i t t j f f t t L t t K t i L f f f 
t t t j j j . . : : : .                 : : i G i i i : , ; ; ; ; i i i i i i i i i i i i i i i i i i i i i i i L i j i t G t j j j f t t t L t t f j i G f f f 
t i i t t i   . : : : .               . . ; i t i i i , : ; ; ; ; i i i f i i i i i i i i i i i i i i i i i i L i t j D t f t j j j f t t t f t t f j i G f f f 
t i i i t :   . : : . .             . : : i i t i i i t : , ; ; ; ; i i i i t t t f L L i i i i i i i i i i i , i j j t j j t j j f f t G t j t j f j ; L f f f 
t t i i t .   . . : .             . , i : i ; t i i i t t : ; ; ; ; i i i i i i i i i i i i i i i i i i i i i f i j E t j j j j j f f t t j t t G f j ; f f f f 
i i i i t .     . : .         . . , i i : i j j i i i t t t : ; ; ; ; i i i i i i i i i i i i i i i i i i i f j i j t j j j j t j f j j t f t t f f j i j f f f 
i i i i t . .   . : .         . . i t i : i t , i i i t t t t : ; ; ; i i i i i i i i i i i i i i i i i i i t i i j t j j j j t K f j K t f t j f f j t t j f f 
i i i i ; . .   . . . . .   . . : t t i : j j i i i i j t L t : , ; ; ; i i i i i i i i i i i i i i i i i i j i i L t j j j j j f f j G t f t D f f j t t f f f 
i i i t : . . . . . . .   . . . i t t i : , j i i i i j t t t t   : ; ; ; i i i i i i i i i i i i i i i i i i j t i j j j j j j f f j j t f j f f f j t t G f f 
i i i t . . . . . . . .   . . : i t t i , : i i t i i t t t t t     , ; ; i i i i i i i i i i i i i i i i i t j j t j t j j j j f f j j t f j f f f j t t E f f 
i i i ; . . . . . . . : . . . , i t i i i . t i j i i t t t t t       , ; ; i i i i i i i i i i i i i i t t j j j t j t j j j j f G j j t f j f L f j L i K f f 
i i t , . . . . . . : . . . . ; i t i : . . ; i , i i t t t t t j .     : ; ; i i i i i i i i i i i i t t t j j i t j f t j j L f j j G t f j f f f j j t j f f 
i i i : . . . . . : , . . . : ; i t i : . . , i : i t t t t j i .         . ; ; i i i i i i i i j . ; t t j j j i t t j j D j E f j t f t f j f f f j j j f f f 
i i i : . . . . . : , . . . : ; i t i . . . : i , i t t t t t : .   . . .   . ; ; i i i i t : . . , , , i j t L i t i t j j j G D j t t j f f f f f j j j f j f 
i i , : . : . . : , , . . . : ; i i i . . . : i ; i j t t t t :     , ; ; . . . i f L ; . . . . : , ; , , i t i t t j t j j j L j t t j j j G f f L j j j L j f 
i t : : . : . . : , , . . . ; ; i i : . . . : i ; ; t t t f t :   . ; ; ; . . . . , : : . . : : , , ; , : , i i j j f t j j j f t t t t j j D f f f j j j j f j 
i t : : . . . . , ; : . . . , ; i i : . . . : t ; i t t t j t . . , ; ; . . . . : . : : . , , ; , , , , : , i t t j f t j j j f t t t t t j f G f D K j j j f j 
i t , : .   . . , ; : . . : , ; i , : . . . : : ; t t t j f : : . ; ; . . . . . . : . . : , ; ; , , ; f , , G t t t f t t t j L t t t t t t f E E E E j j j f j 
i ; , : : : : : ; i : . . : ; ; i : , . . . : , i t t f j t . . : , : . . . . . . . . . , ; ; ; , , D D , , i j t j j t t t t L t t t t t E j E E f E E j j j f 
t ; , : : : : , i i : . . , ; ; i : ; : . . : i i t t j j :   . : : . . . . . .   . . : , , ; , , ; D E , , i E t f j t t t t j t t t E E E t f E E E K j j j f 
t ; , : : : : ; i i : . . , ; ; , : ; . . . : i i t f t f . . . : . . . .         . . : , , , ; ; L E E , ; , t t L t t t t t j f j E E E D ; t ; ; ; ; ; j j j 
t ; , : : : : i i ; : . . , ; ; : : ; . . . : i ; j j j , . . : . .               . : , , , ; ; f G E D , f i t t L t t t t t t t E E ; ; ; ; ; L ; ; ; ; ; j j 
i i , : : : ; i i , . . . , ; ; : : i . . . i i : j t j . . : . .               . . : , , ; ; ; L D E j , j t t t f t t t t t E f t ; ; ; ; ; ; ; L ; ; ; ; ; j 
i i , : : : i i i , . . . , ; , : : i . . . i i i j t .   . . .                 . . : , , ; ; f G E E t , t f t t f ; t j t t ; ; t t ; ; ; ; ; ; ; ; t ; ; ; ; 
i i ; : : : i i i : . . . , ; : : : , . . : i i t t L     , . .                 . . : , , ; i L G E D t ; t j t t f , t f t t ; ; L t t i t ; ; ; ; ; ; ; ; ; ; 
i i ; : : , t i i : . . . , , : : : : . . : i i t L     . .                 : . . . , , ; ; t G D E j t i t i t j f , t f t t ; ; ; G t t f ; ; ; t j j i ; ; ; 
i i ; : : i t t i : : . : , , : : : : , , ; i t t .     ,                 . : . . , ; i ; i G G E E j t t t ; t f f ; t f t t ; f ; ; L t t t t j L j j ; ; ; ; 
i i ; : : i t i i : , . : , , : : . . : : i i t :     . .                     . . , ; i i t G G E E t t t f t D L f , t G t t t ; ; ; ; ; ; ; ; i t ; ; ; f f j 
; ; , : : t t t i : , . : , , : . . : i , i i f .   . .                       . . , i i t G G G E j t t t j L E L f , t K j t j ; ; ; ; ; i ; t t t ; i t ; i f 
; ; , : , t t t ; : , . : , : : . : : : j ; i t     . .                   .   . . , i i i L G E D t t t t G E E L f t t t f t L ; ; ; ; ; ; i t t t ; t t t i ; 
; ; , : i t t i ; : ; . : , : : . : : : t : i .   . . .                       . . . ; ; t G G E j t t t G D E : j f j t t f t t ; ; ; ; i i i i t i : i t t i ; 
; ; , : i t t i ; : ; . : , : : : t : ; t f i . . . :                         . . . ; i G G G E j t t G D E , . L f j t t i f t t f ; ; i t t t t ; i i i ; ; i 
; ; ; : i t t i ; , ; . : , : : : : , , t i ;   . . .                         . . : i i G G E E t t G G E , t   ; f f t t j ; j t t f f i t t t t t i t t t i ; 
; ; ; , t t t i ; ; ; . : : : : ; : , : t , t   . .                       . . : : , i t G G E j t E G D , :     ; i f t t t ; ; ; t t f f f f j t t i t t t i ; 
; ; ; ; t t i i ; ; ; . : : : : : , ; , t , . i .                         . : : : , i L G G E j j G D , : L   : ; ; G j t t j ; ; ; i i L L f f f f t i t t ; ; 
; ; ; i i i i i i ; i : . : : : . , ; , j , .   ; :   i .                   : : : ; i L G D E j G G E . i t . ; ; ; ; L t t t D ; ; ; ; ; ; i t j f f f i ; ; ; 
; ; ; i t i i i i ; i : . : : ; . , ; , j , .     . . .                     . . . ; f G G D f E G D . : . . t ; ; ; ; ; ; j j t f i i i i i i i i i i t f j ; ; 
; ; ; i t i i i i i i , . : : t . ; ; ; ; , .                                   . ; L G G E j G D : j . . . i t . . . : ; i ; ; , , ; ; ; ; ; ; i i i ; ; t j ; 
; ; ; i i i i i i i i ; . : : t : ; ; i ; , .     .                             . i G G D E G G : . . . . i . j ; . . . . : : : , ; ; ; ; ; ; ; ; ; i t i ; i i 
; ; ; j j i i i i i i ; . : : t : ; ; j ; ; .     .                             , t G G D E G D . . . i . . . , . . . : : ; ; ; ; ; ; i i i i i ; ; ; ; i t i i 
; i i t i j t i i i i ; . : : f t i i ; j ; ; : . .                           . ; G G G D G L . . ; . .           . . . . : ; ; ; ; i t i i t i ; ; i t i t t t 
; ; ; ; i i t i i i i ; , , , i j f j i , : .     : .                         : ; L G D E L , t . .     . .             . : : , ; ; ; i i i i i ; ; t t i i i i 
i ; ; ; i ; ; i t t j t ; , , , : . .               . : .                   : ; ; L L G L i .   . . : ; ; ; ; , , , : : . . : : , ; i i i i i i , , i i i i t t 
i i ; ; ; ; ; ; i ; : : . . . . . .                     . .     . . . . : , i t ; , . .     . . . : ; ; ; ; ; ; ; ; ; ; ; ; : : : , ; i i i i i ; ; t t i i i t 
i i i i ; ; ; ; ; ; ; i i ; ; ; , , , : : . .             . : . . . .                     . . . : , ; ; ; ; ; ; ; ; ; ; ; ; ; ; , , , ; i i ; ; ; ; i i i t i ; 
i i i i i i ; ; ; ; ; ; i i i ; ; ; ; ; ; ; , : .   . , . . . . :               . . . . . . . . : ; ; ; ; ; ;   ; ; ; ; ; ; ; ; ; ; ; , ; ; ; ; ; ; ; ; i i i ; 
i i i i i i i i ; ; ; ; ; i i ; ; ; ; ; ; ; ; ; ; ; : , ; ; ; ; , ; : : : . . . . . . . . . . : ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; 
i i i i i i i ; ; ; ; ; ; ; i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; , : . . . . . : , ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; ; ; ; ; ; ; 
i i i i i i i ; ,   ; ; ; ; ; t ; ; ; ; ; ; ; , ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; i , : : : : ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; i ; ; ; ; ; 
i i i i i i i ; ; , ; ; ; ; ; ; t ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; i i i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i i ; ; 
i i t i i i i ; ; ; ; ; ; ; ; ; i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; i i i i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i ; ; ; 
i i i i i i i ; ; ; ; ; ; ; ; ; ; t ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; i ; ; i i i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i ; ; ; 
i i i j i i i ; ; ; ; ; ; ; ; ; ; ; t ; ; ; ; ; ; ; ; ; ; i t t ; ; ; ; ; ; i ; ; i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; i i ; ; ; 
i i i j i i i ; ; ; ; ; ; ; ; ; ; ; i i i i i ; ; ; i ; ; ; t t ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; t ; ; ; 
i i i j i i i i ; ; ; ; ; ; ; ; ; ; ; t ; ; ; i ; ; i i ; ; i ; ; ; ; ; ; i i i ; ; i i t i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; 
i i i j t i i ; ; i ; ; ; ; ; ; ; ; ; i i ; ; ; i ; ; ; ; ; ; ; ; ; ; ; i i i i ; ; t i i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; i i i i i i ; 
i i i j j i i ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; i ; ; ; ; i i t i ; ; ; i i i i ; t t i t i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; t t i ; ; ; i i t t t ; ; 
i i i j j i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; i i i i ; ; i t t t i i ; ; i i i i ; i t t i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i t t i ; ; ; t t j t i i i 
; i i j j i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i t t t ; ; ; i t i t t i ; ; ; ; ; i ; ; i i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i ; ; ; i t t t t t t i 
; i i j j i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; t t i j t t ; ; i t t t i ; ; ; ; ; ; i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; i i t t t t t t 
i ; i j j t i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i t j f j i ; ; i i t t ; ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; . ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; i t t t j j i ; 
i ; t j j j i ; ; ; ; ; ; ; ; ; ; . ; ; ; ; ; i i i j j t ; ; ; ; i i ; ; ; ; ; ; ; i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; i i t i j j i i 
i ; t j j j i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i j j t i ; ; ; ; ; ; ; ; ; ; ; ; ; t ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i ; ; i i i j t i i 
i ; j j j j i ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; i j j j t ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i ; ; i i i i t t i 
i ; j j j j i ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; i j j j t ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i ; i i i i t t i 
i i j j j j i ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; i j j j t i ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i ; i i i i t t t 
i i j j j j i ; ; ; ; ; ; ; ; ; ; ; i i ; ; ; ; ; i j j j j t ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i i t i t t t t 
i i j j j j i ; ; ; ; ; ; ; ; ; ; i i i i ; ; ; ; t j j j j t i ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i i i t t t t t t t 
i t j j j j i i ; ; ; ; ; ; ; ; ; i i i i ; ; ; ; t j j j j j i ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; i t t i i t j j t t t 
i t j j j j i i ; ; ; ; ; ; ; ; ; i i i i ; ; ; ; t j j j j j t ; ; ; i ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i t j t i t j t t t t 
i j j j j j i ; ; ; ; ; ; ; ; i i i i i i i ; ; ; t j j j j j j ; ; ; i i ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; i t t t t t j j t t t 
i j j j j j i i ; i ; ; i i i i i i i i i i i i i t j j j j j j i ; ; ; ; ; ; ; ; ; ; ; ; ; ; i ; ; ; ; ; ; ; i ; i ; ; ; ; ; ; ; ; ; ; i i t t j t t j t t t t 
t j j j j j i i i i i i i t t t t t t t t t t t i j j j f j j j t ; ; ; ; ; ; ; ; ; ; ; ; ; ; i i ; ; ; ; ; i t i t i ; ; ; ; ; ; ; ; ; i i t t t t t t t t t t 
j j j j j j i i i i i t t t t t t t t t t t t t t j f f f f f j j ; i ; ; ; ; ; ; ; i ; ; ; ; ; i ; ; ; ; ; ; t t t i i i i i ; ; ; ; ; i i t t t i t t j j j t 
j j j j j j i i i i i t t t t t t t t t t t t i i j f f f f j j j i i i i i i ; ; ; ; ; ; ; ; ; i ; ; ; i t i i t t i t t i i ; ; i i i i i t t t t t j j j j t 
j j f f f f i i i i i i i t t t t t t t t i i i i j j f f f j j j i i i t t i i i i ; ; ; ; ; ; ; i ; ; i t t i i i t t t t i i i i i t t t t t t t j j j j j j 
f f f f f f i i i i i i i t t t t t t t i i i i i j j j f j j f j t i i i i i i i i i t i i ; ; ; i ; i t t t t i i t t t i i i i i i t t i t t t t j j j j j j 
f f f f f f t i i i i i i i t t t t t t t t i i i j j j f j j j j t i i i i i i t i t t t i i i i i i i i t i i t t t i i i i i i i i i i i t t t j j f f f j j 
f f f f f j i i i i i i i i t t t i t t t t i i i j j j f j j j j t i i i i i i t t t t t i i i i i t i i i t t t t t t t i i i i i i i i i t t t j j j f j j j 
*/
#pragma GCC optimize(2)
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int Rea=1e5+3;
struct Rin
{
    char c;
    inline char gc()
    {
        static char rea[Rea];
        static char *head,*tail;
        return head==tail&&(tail=(head=rea)+fread(rea,1,Rea,stdin),head==tail)?EOF:*head++;
    }
    inline Rin&operator >>(int &x)
    {
        x=0;
        bool tag=false;
        for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
        for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');
        if(tag)x=-x;
        return *this;
    }
    inline Rin&operator >>(LL &x)
    {
        x=0;
        bool tag=false;
        for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
        for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');
        if(tag)x=-x;
        return *this;
    }
    inline Rin&operator >>(string &x){x.clear();for(c=gc();c>'z'||c<'a';c=gc());for(;c>='a'&&c<='z';c=gc())x.push_back(c);return *this;}
}rin;
inline void jh(int &x,int &y){if(x^y)x^=y^=x^=y;return;}
inline void jh(LL &x,LL &y){if(x^y)x^=y^=x^=y;return;}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
inline LL min(LL x,LL y){return x<y?x:y;}
inline LL max(LL x,LL y){return x>y?x:y;}
const int N=1e2+3;
const int M=1e9+7;

int n,q;
int b[N];
int c[N];
LL d[N];

int smb[N];
int smc[N];

int f[N][N*N];
int g[N][N*N];
map<int,int>pri;
#define rmod(x) if(x>=M)x-=M;
#define lmod(x) if(x<0)x+=M;
inline void work()
{
    //前缀和严格变小，/sum > /sum
    rin>>n;for(int i=1;i<=n;i++)rin>>c[i];for(int i=1;i<n;i++)rin>>b[i];
    rin>>q;for(int i=1;i<=n;i++)smb[i]=smb[i-1]+b[i],smc[i]=smc[i-1]+c[i];
    for(int i=1;i<=n;i++)d[i]=d[i-1]+smb[i-1];
    int l=1e5,r=1e5;
    for(int i=1;i<=n;i++)r=min(r,(smc[i]-(int)(d[i]))/i),l=min(l,-(int)(d[i])/i);
    for(int x=l-1;x<=r;x++)
    {
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        int ans=0;
        for(int i=1;i<=n;i++)d[i]=d[i-1]+x+smb[i-1];
        for(int i=1;i<=n;i++)d[i]=max(d[i],0LL);
        // for(int i=1;i<=n;i++)printf("%lld ",d[i]);puts("");
        for(int i=0;i<=smc[1];i++)g[0][i]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=d[i];j<=smc[i];j++){f[i][j]=g[i-1][j]-((j-c[i]-1<0)?0:g[i-1][j-c[i]-1]);lmod(f[i][j]);}
            if(i==n)for(int j=d[i];j<=smc[i];j++){ans+=f[i][j];rmod(ans);}
            else for(int j=0;j<=smc[i+1];j++){g[i][j]=((j==0)?f[i][j]:g[i][j-1]+f[i][j]);rmod(g[i][j]);}
        }
        pri[x]=ans;
    }
    for(int i=1;i<=q;i++){int x;rin>>x;if(x>r)puts("0");else printf("%d\n",pri[max(x,l-1)]);}
    return;
}
int main()
{
    work();
    return 0;
}
