Və yenə də kədər...

Giriş

Əvvəlcə çoxluq $S$ boş olur. Birinci sətirdə əməliyyatların sayı olan $n$ (1 \leq n \leq 300\ 000) tam ədədi var. Sonrakı $n$ sətirdə hər biri aşağıdakı formalardan birində olan bir əməliyyat verilir:

• "+ i"

• "? l r"

"? l r" əməliyyatı \text{sum}(l, r) sorğusuna uyğundur.

Əgər "+ i" əməliyyatı birinci əməliyyatdırsa və ya başqa bir "+" əməliyyatından sonra gəlirsə, bu $\text{add}(i)$ əməliyyatına uyğundur. Lakin əgər bu əməliyyatdan əvvəl "?" sorğusu olubsa və həmin sorğunun cavabı $y$ olubsa, onda əməliyyat \text{add}((i + y) \bmod 10^9) formasını alır.

Sorğulardakı və əlavə əməliyyatlarındakı bütün parametrlər $0$ və 10^9 (hər ikisi daxil olmaqla) aralığındadır.

Çıxış

Hər bir sorğu ("? l r") əməliyyatının cavabını çıxışa bir sətirdə yazın.

Nümunələr